Proving an identity involving factorials

I have stumbled upon the following statement and have verified it computationally for many $n$ (up to n=500, it took a long time for my computer to do out all of the math), yet I have no idea how to go about proving it.

$$\sum _{ i=0 }^{ n } \sum _{ j=0 }^{ n } \frac { { ((2n)! })^{ 2 }(-1)^{ i+j }(2i+2j)! }{ (n-i)!(n-j)!(2i)!(2j)!2^{ i+j }(i+j)! } =\frac { (4n)! }{ { 4 }^{ n }(2n)! } $$

One thing to note is that if we multiply the top and bottom of the fraction by $(i)!$, $(j)!$, and $(n!)^2$, then certain terms simplify into the factorial definition of the binomial coefficient, so the sum is also expressible as:

$$\sum _{ i=0 }^{ n } \sum _{ j=0 }^{ n } (-1)^{ i+j } \binom{n}{i}\binom{n}{j} \frac { { ((2n)! })^{ 2 }}{(n!)^2}\frac{(i)!}{(2i)!}\frac{(j)!}{(2j)!}\frac{(2i+2j)! }{2^{ i+j }(i+j)! } =\frac { (4n)! }{ { 4 }^{ n }(2n)! } $$

Also, let us define $P(n)$ to be equal to the product of the first $n$ positive odd numbers (or more specifically, $P(n)=(2n-1)!!$). We can use the explicit formula $P(n)=\frac{(2n)!}{2^n n!}$ (see here for explanation) to rewrite various expressions: $$\frac{(2i+2j)! }{2^{ i+j }(i+j)! }=P(i+j)$$ $$\frac{((2n)!)^2}{(n!)^2}=(P(n))^2 2^{2n}$$ $$\frac{(i)!}{(2i)!}=\frac{1}{2^i P(i)}$$ $$\frac{(4n)!}{4^{n}(2n)!}=P(2n)$$

And so the statement can be rewritten as: $$ \sum _{ i=0 }^{ n } \sum _{ j=0 }^{ n } (-1)^{ i+j } \binom{n}{i}\binom{n}{j} \frac{2^{2n}(P(n))^2 P(i+j)}{2^{i+j}P(i)P(j)}=P(2n) $$

Interestingly enough, this proves that the left hand side must be an integer (see here for an explanation), which i believe is a step in the right direction.

This is all just random stuff I have been trying to attempt to prove the identity although so far I have not gotten very far. If anyone has any idea on how I could prove this identity or even just begin to prove the identity, please help me out! Any and all help is appreciated!

Edit, here is some more work done on the topic:

Let us define: $$R_n = \sum _{ i=0 }^{ n } \sum _{ j=0 }^{ n } \frac { { ((2n)! })^{ 2 }(-1)^{ i+j }(2i+2j)! }{ (n-i)!(n-j)!(2i)!(2j)!2^{ i+j }(i+j)! }$$

I am currently trying to prove that $R_n=P(2n)$. Since $P(n)$ is the product of the first $n$ odd integers, and $2n-1$ is the $n$th odd integer, it follows that $P(2(n+1))=P(2n+2)=P(2n) \cdot (4n+1) \cdot (4n+3)$. Thus (since the base case works, and you can confirm that if you truly want), a statement equivalent to what I am trying to prove is: $$R_{n+1}=(4n+1)(4n+3)R_{n}$$

Solution 1:

Consider the polynomial $$ f_n(x)=\left(x^2+1-\frac{\left(x+1\right)^2}{2}\right)^{2n}. $$ The left and right hand sides of the OP's identity each compute the coefficient of $x^{2n}$ in $f_n(x)$.

One the one hand, we can expand $f_n$ using the trinomial and binomial theorems: \begin{align*} f_n(x)&=\sum_{a+b\leq 2n}\frac{(2n)!}{a!b!(2n-a-b)!}x^{2a}\left(x+1\right)^{2(2n-a-b)}\frac{(-1)^{2n-a-b}}{2^{2n-a-b}}\\ &=\sum_{\substack{a+b\leq 2n\\r\leq 4n-2a-2b}}\frac{(2n)!}{a!b!(2n-a-b)!}{4n-2a-2b\choose r}\frac{(-1)^{2n-a-b}}{2^{2n-a-b}}x^{2a+r}. \end{align*} To get $x^{2n}$, we need $r=2n-2a$, so that $a\leq n$. Additionally, $r=2n-2a$ and $r\leq 4n-2b-2b$ imply $b\leq n$, so we are summing over $0\leq a,b\leq n$. Make the substitution $i=n-a$, $j=n-b$ (so that $r=2i$). In terms of $i$ and $j$, the sum is over $0\leq i,j\leq n$. This shows that the coefficient of $x^{2n}$ is the left hand side of the OP's identity.

On the other hand, we can simplify $f_n$: \begin{align*} f_n(x)&=\left(\frac{(x-1)^2}{2}\right)^{2n}\\ &=\frac{(x-1)^{4n}}{4^n}. \end{align*} The binomial theorem then shows the coefficient of $x^{2n}$ is the right hand side of the OP's identity.

Solution 2:

The equation

$$ \sum_{i = 0}^{n}\sum_{j = 0}^{n} (-1)^{i + j} \binom{n}{i} \binom{n}{j} \frac{2^{2n}(P(n))^{2}P(i + j)}{2^{i+j}P(i)P(j)} = P(2n) $$

is a prime suspect for combinatorial proof (combinatorial proof). The idea would be to find a quantity that both sides are counting.

Particularly, the quantity $\binom{n}{i}\binom{n}{j}$ is what suggests the nature of the sum. If we let $$f(i, j) = (-1)^{i + j}\frac{2^{2n} P(n)^{2} P(i + j)}{2^{i+j} P(i)P(j)}$$ then it reduces to $$ \sum_{i = 0}^{n}\sum_{j = 0}^{n}\binom{n}{i}\binom{n}{j}f(i,j) $$ This is then a sum of $f(i,j)$ over a very particular set: the set of two-part partitions of subsets of $\{1,2,\dots 2n\}$. This set is less complicated than it sounds: any element is just a pair of subsets, one of $\{1, 2, \dots n\}$ and the other of $\{n + 1, n+2, \dots 2n\}$. Why this makes sense is not clear.

As for simplifying $f(i,j)$, we can break it up into pieces. The first thing to note is the $2^{i + j}$. The number of subsets of a set with $k$ elements is $2^{k}$ (more information). Therefore, we might consider that $$\frac{2^{2n}}{2^{i+j}} = 2^{2n - i - j} = (2^{n - i})(2^{n - j})$$ may be a good way to decompose it. Then the quantity represents the number of subsets of the remaining elements after removing $i$ from the first $n$ and $j$ from the second.

Also, this suggests the origin of $(-1)^{i + j}$. When summing over certain sets of subsets, we run into sign changes due to the principle of inclusion-exclusion (also known as PIE).

The significance of $\left(P(n)^2 \frac{P(i + j)}{P(i)P(j)}\right)$ then is a bit clearer. Consider the relation between $P(2n)$ and $P(n)^{2}$. Since $P$ is nonlinear, the difference is analogous to a crossterm (e.g $(x+y)^{2} - (x^{2} + y^{2})$). Therefore, the sum may be quantifying the size of this crossterm. Indeed, if we move $P(n)^{2}$ to the other side, we get:

$$ \sum_{i = 0}^{n}\sum_{j = 0}^{n} \binom{n}{i} \binom{n}{j} \left((-1)^{i + j} \cdot 2^{2n - i - j}\right) \frac{P(i + j)}{P(i)P(j)} = \frac{P(n + n)}{P(n)P(n)} $$

Or, letting $g(i,j) = \frac{P(i + j)}{P(i)P(j)}$,

$$ \sum_{i = 0}^{n}\sum_{j = 0}^{n} \binom{n}{i} \binom{n}{j} \left((-1)^{i + j} \cdot 2^{2n - i - j}\right) g(i,j) = g(n,n) $$

This still does not have a clear interpretation, but it is getting there. The next step would be to find a concrete interpretation to one of $P$ or $g$ (an interpretation of the other would likely follow).

Update:

It turns out that for even integers $g$ has a particularly nice interpretation. Note that $$ (2k)!! = (2k)(2k-2) \dots (4)(2) = 2^{k}[(k)(k-1) \dots (2)(1)] = 2^{k} k! $$ Therefore, $$ g(2i,2j) = \frac{2^{i+j}(i+j)!}{2^{i}2^{j} \ i! \ j!} = \frac{(i+j)!}{i! \ j!} = \binom{i+j}{i} $$ which is the number of $i$ element subsets of $\{1, 2, \dots i+j\}$. Unfortunately it does not work so nicely for odd integers ($g(i,j)$ is typically not an integer when at least one of $i, j$ is odd).

The double factorial has a number of interpretations, particularly for odd values (see wikipedia). Also of potential use is a paper about relevant identities (A combinatorial survey of identities for the double factorial).

Solution 3:

Let, $$S_1(n)=\sum _{ i=0 }^{ n } \sum _{ j=0 }^{ n } \frac { { ((2n)! })^{ 2 }(-1)^{ i+j }(2i+2j)! }{ (n-i)!(n-j)!(2i)!(2j)!2^{ i+j }(i+j)! } \\ S_2(n) =\frac { (4n)! }{ { 4 }^{ n }(2n)! } $$
Notice that $S_1(0)=S_2(0) = 1$. Secondly observe by elementary manipulations that, $$ S_2(n+1) = (1+4n)(3+4n)S_2(n)$$ Substitute $S_1(n)$ into the same recurrence and observe it also satisfies, $$S_1(n+1) = (1+4n)(3+4n)S_1(n)$$ The two sequences, $S_1$ and $S_2$, agree at $n=0$ and one may compute their $(n+1)^\textrm{th}$ values by the same recurrence it must be that the two sequences agree for all $n$ by induction. One concludes that, $S_1(n) = S_2(n)$.

Additional Remarks: To help understanding I will further sketch how to verify the recurrence for $S_1$. I wish to avoid typing endlessly so will not give all the algebra. Also the exercise is far harder than usual!

Start from $S_1(n+1)$ and start manipulating, $$ S_1(n+1) = \sum _{ i=0 }^{ n+1 } \sum _{ j=0 }^{ n+1 } \frac { { ((2n+2)! })^{ 2 }f(i,j)}{ (n+1-i)!(n+1-j)!} $$ Here $f(i,j)$ is used just to shorten expressions. Compare to above for a definition. Continuing, $$ S_1(n+1) = \sum _{ i=0 }^{ n+1 } \sum _{ j=0 }^{ n+1 } \frac { { ((2n+2)! })^{ 2 }f(i,j)}{ (n+1-i)!(n+1-j)!}\\ = \sum _{ i=0 }^{ n+1 }\left[ \frac { { ((2n+2)! })^{ 2 }f(i,n+1)}{ (n+1-i)!}+ \sum _{ j=0 }^{ n } \frac { { ((2n+2)! })^{ 2 }f(i,j)}{ (n+1-i)!(n+1-j)!}\right]\\ = \sum _{ i=0 }^{ n+1 }\left[ \sum _{ j=0 }^{ n } \frac { { ((2n+2)! })^{ 2 }f(i,n+1)}{ (n+1) (n+1-i)!}+ \frac { { ((2n+2)! })^{ 2 }f(i,j)}{ (n+1-i)!(n+1-j)!}\right]\\ =\left[ \sum _{ j=0 }^{ n } \frac { { ((2n+2)! })^{ 2 }f(n+1,n+1)}{ (n+1)}+ \frac { { ((2n+2)! })^{ 2 }f(n+1,j)}{ (n+1-j)!}\right]+ \sum _{ i=0 }^{ n}\left[ \sum _{ j=0 }^{ n } \frac { { ((2n+2)! })^{ 2 }f(i,n+1)}{ (n+1) (n+1-i)!}+ \frac { { ((2n+2)! })^{ 2 }f(i,j)}{ (n+1-i)!(n+1-j)!}\right]\\ = \sum _{ i=0 }^{ n} \sum _{ j=0 }^{ n }\frac { { ((2n+2)! })^{ 2 }f(n+1,n+1)}{ (n+1)^2}+ \frac { { ((2n+2)! })^{ 2 }f(n+1,j)}{ (n+1)(n+1-j)!}+ \frac { { ((2n+2)! })^{ 2 }f(i,n+1)}{ (n+1) (n+1-i)!}+ \frac { { ((2n+2)! })^{ 2 }f(i,j)}{ (n+1-i)!(n+1-j)!} $$ Placing this into the recurrence, putting the polynomial on the front of $S_1(n)$ should give a remaining double sum. The double sum indeed vanishes and my computer is currently doing the algebra to show that...