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 $$$n$$$ and $$$m$$$, 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 $$$0$$$ to $$$\lfloor m/2 \rfloor$$$ or $$$\lfloor n/2 \rfloor$$$. What we can do is to introduce variables $$$a=n-2j$$$ and $$$b=m-2i$$$, after which the expression under the sum changes to
As we want to sum it up over all $$$i,j,a,b$$$ such that $$$a + 2j = n$$$ and $$$b + 2i = m$$$, we can keep track of these equations with two formal variables $$$x$$$ and $$$y$$$. 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 $$$s=a+b$$$ 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 $$$x^2$$$ and $$$y^2$$$, we have an expression of form $$$G(x, y) = A(x, y) \cdot B(x^2, y^2)$$$.
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 $$$A'(x^2, y^2) \cdot B(x^2, y^2)$$$, so that we can go back from $$$(x^2, y^2)$$$ to $$$(x, y)$$$ and analyze them as $$$A'(x, y) \cdot B(x, y)$$$. 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 $$$x$$$, and the second summand only has odd powers of $$$x$$$. In our case, we need to apply it first to the variable $$$x$$$, and the to $$$y$$$. 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 $$$4$$$ distinct summands in the numerator correspond to all possible combinations of parities of powers of $$$x$$$ and $$$y$$$. 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) $$$[x^n y^m]$$$ of the function
This function is very similar to
about which we already know that $$$[x^n y^m] G(x, y) = \binom{n+m}{n}^2$$$. Indeed, we can notice that
therefore
from which it follows that
This allows to solve the problem in $$$O(1)$$$ per $$$(n, m)$$$ pair with $$$O(n+m)$$$ 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 $$$f(n, m)$$$ relates to $$$f(n-1,m)$$$ and $$$f(n,m-1)$$$, 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 $$$\binom{i+j}{i}^2$$$ directly, without using Legendre polynomials.
Consider a bivariate polynomial $$$Q_n(x, y)$$$ defined as
We need to sum it up over all $$$n$$$, and we know from Legendre polynomials that $$$Q_n(x) = (y-x)^n P_n(\frac{y+x}{y-x})$$$.
But let's analyze $$$Q_n(x, y)$$$ on its own:
This expands into
Note that
hence we want to compute the sum
Let's sum up over $$$n$$$ for each fixed $$$k$$$:
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.