By adamant, history, 6 months ago, 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

$\binom{i+j}{j}^2 \binom{a+b}{a}.$

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

$[x^n y^m] \sum\limits_{i,j,a,b} \binom{i+j}{i}^2 \binom{a+b}{a} x^{2j+a} y^{2i+b} = [x^n y^m]\left(\sum\limits_{a, b} \binom{a+b}{a} x^a y^b\right) \left(\sum\limits_{i,j} \binom{i+j}{i}^2 x^{2j} y^{2i}\right).$

This is the product of two generating functions. The first one is standard and collapses with $s=a+b$ substitution:

$\sum\limits_{a, b} \binom{a+b}{a} x^a y^b = \sum\limits_s (x+y)^s = \frac{1}{1-x-y}.$

The second generating function is trickier, and collapses into

$\sum\limits_{i,j} \binom{i+j}{i}^2 x^{2j} y^{2i} = \frac{1}{\sqrt{1-2(y^2+x^2)+(y^2-x^2)^2}}.$

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

$\boxed{ [x^n y^m] \frac{1}{1-x-y}\frac{1}{\sqrt{1-2(y^2+x^2)+(y^2-x^2)^2}}}$

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

$A(x) = \frac{A(x)+A(-x)}{2} + \frac{A(x)-A(-x)}{2},$

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

$(1-x-y)(1+x-y)(1-x+y)(1+x+y),$

meaning that the numerator must be

$(1+x-y)(1-x+y)(1+x+y),$

which expands to

$\boxed{\frac{1}{1-x-y} = \frac{[1-x^2-y^2] + [x-x^3+xy^2] + [y+x^2y-y^3] + [2xy]}{(1-x-y)(1+x-y)(1-x+y)(1+x+y)}}$

#### 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

$(1-x-y)(1+x-y)(1-x+y)(1+x+y) = 1-2(y^2+x^2)+(y^2-x^2)^2,$

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

$F(x, y) = [1-2(y+x)+(y-x)^2]^{-3/2}.$

This function is very similar to

$G(x, y) = [1-2(y+x)+(y-x)^2]^{-1/2},$

about which we already know that $[x^n y^m] G(x, y) = \binom{n+m}{n}^2$. Indeed, we can notice that

$\begin{cases} \frac{\partial}{\partial x} G(x, y) = (1-x+y) F(x, y), \\ \frac{\partial}{\partial y} G(x, y) = (1+x-y) F(x, y), \end{cases}$

therefore

$F(x, y) = \frac{1}{2}\left[\frac{\partial}{\partial x} G(x, y) + \frac{\partial}{\partial y} G(x, y)\right],$

from which it follows that

$\boxed{[x^n y^m] F(x, y) = \frac{1}{2}\left[(n+1)\binom{n+m+1}{n+1}^2 + (m+1)\binom{n+m+1}{m+1}^2\right]}$

This allows to solve the problem in $O(1)$ per $(n, m)$ pair with $O(n+m)$ pre-computation:

code

#### Alternative approaches

The answer to the whole problem can be further simplified as

$\boxed{f(n, m) = \left\lfloor(n+m)/2+1 \right\rfloor \binom{\lfloor n/2 \rfloor + \lceil m/2 \rceil}{\lfloor n/2 \rfloor} \binom{\lfloor m/2 \rfloor + \lceil n/2 \rceil}{\lfloor m/2 \rfloor}}$

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
1. Is there a sufficiently simple way to solve this problem without just "observing" some weird facts?
2. 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

$Q_n(x, y) = \sum\limits_{k=0}^n \binom{n}{k}^2 x^k y^{n-k} = [t^n] (x+t)^n (y+t)^n.$

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:

$[t^n](x+t)^n (y+t)^n = [t^n](t(t+x+y)+xy)^n.$

This expands into

$\sum\limits_k \binom{n}{k} x^k y^k [t^k] (t+x+y)^{n-k} = \sum\limits_k \binom{n}{k} \binom{n-k}{k} x^k y^k (x+y)^{n-2k}.$

Note that

$\binom{n}{k} \binom{n-k}{k} = \binom{n}{k, k, n-2k} = \binom{n}{2k} \binom{2k}{k},$

hence we want to compute the sum

$\sum\limits_{n, k} \binom{n}{2k} \binom{2k}{k} x^k y^k (x+y)^{n-2k}.$

Let's sum up over $n$ for each fixed $k$:

$\sum\limits_{n} \binom{n}{2k} (x+y)^{n-2k} = \sum\limits_{t} \binom{2k+t}{2k} (x+y)^{t} = \frac{1}{(1-x-y)^{2k+1}}.$

Thus, we want to compute

$\sum\limits_k \binom{2k}{k} \frac{x^k y^k}{(1-x-y)^{2k+1}}.$

On the other hand we know that

$\sum\limits_k \frac{x^k}{4^k} \binom{2k}{k} = \frac{1}{\sqrt{1-x}},$

thus the sum above compacts into

$\frac{1}{1-x-y} \frac{1}{\sqrt{1-4\frac{xy}{(1-x-y)^2}}}= \boxed{\frac{1}{\sqrt{(1-x-y)^2-4xy}}}$

which then expands into the same expression in the denominator.  Comments (12)
 » Why?
 » Great blog as usual (no sarcasm)
•  » » kidding of course, yes sarcasm
 » interesting!
 » I understood only the formula at the very end
 » 6 months ago, # | ← Rev. 3 →   did you try asking our polynomial god Karry5307He can solve all polynomial problems that exist in this world, assuming there is an editor here.
 » What the fuck is even that?
•  » » A simple math problem.
•  » » » you need stop learning useless algo.
•  » » » » but he is red now...
•  » » » » This blog isn't even about some algorithm...
 » And I thought I was good at maths.