Solving the "simple math problem" with generating functions
source link: https://codeforces.com/blog/entry/117195
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Hi everyone!
Some time ago the following "simple math problem" was shared in a Discord chat:
As a lover of simple math problems, I couldn't just pass by this problem. It turned out much harder than any other genfunc problem that I solved before, as the structure of the answer depends on the parity of and , and it's not very natural to track it through genfuncs. It took me few months, I even called for help from higher powers (i.e. sent a pm to Elegia) but I finally have a solution that I somewhat like.
Finding a closed-form genfunc
First of all, it's really inconvenient to sum up from to or . What we can do is to introduce variables and , after which the expression under the sum changes to
As we want to sum it up over all such that and , we can keep track of these equations with two formal variables and . Then, the sum that we're interested in expresses as
This is the product of two generating functions. The first one is standard and collapses with substitution:
The second generating function is trickier, and collapses into
Unfortunately, I don't have a simple explanation to it, as it is obtained via reduction to a well-known bivariate generating function for Legendre polynomials (see this Mathematics Stack Exchange question for details). So, the problem reduces to finding
Adding series multisection
Since the second function in the product only depends on and , we have an expression of form .
It would make sense to do a series multisection (aka roots of unity filter) to represent it as a combination of summands that look like , so that we can go back from to and analyze them as . This way we detach from possible dependence on the parities of the powers of coefficients. The multisection is generally done as
where the first summand only has even powers of , and the second summand only has odd powers of . In our case, we need to apply it first to the variable , and the to . However, we can do a little shortcut, as after doing so, the common denominator of the resulting expression should be
meaning that the numerator must be
which expands to
Solving for parities
The distinct summands in the numerator correspond to all possible combinations of parities of powers of and . But what is really striking here is that the denominator expands to
meaning that it is exactly the expression under the square root of the second function multiplier. Therefore, the full problem reduces to finding (and computing an appropriate linear combination of) of the function
This function is very similar to
about which we already know that . Indeed, we can notice that
therefore
from which it follows that
This allows to solve the problem in per pair with pre-computation:
Alternative approaches
The answer to the whole problem can be further simplified as
Thanks to Endagorion for telling me about this form! One can prove it by inspecting how relates to and , but apparently there is also a bijective proof. You may also refer to this publication for further details and alternative proofs.
Follow-up questions to interested audience
- Is there a sufficiently simple way to solve this problem without just "observing" some weird facts?
- Is there a more direct way to find the closed form on the second function? (see this question).
UPD: I found out how to compute the genfunc for directly, without using Legendre polynomials.
Consider a bivariate polynomial defined as
We need to sum it up over all , and we know from Legendre polynomials that .
But let's analyze on its own:
This expands into
Note that
hence we want to compute the sum
Let's sum up over for each fixed :
Thus, we want to compute
On the other hand we know that
thus the sum above compacts into
which then expands into the same expression in the denominator.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK