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}$$

• Maple outputs $$\sum _{i=0}^{n}{\frac { \left( \left( 2\,n \right) ! \right) ^{2} \left( -1 \right) ^{i}{\mbox{_2F_1}(-n,1/2+i;\,1/2;\,1/2)}}{ \left( n-i \right) !\,n!\,{2}^{i}i!}}$$ for the double sum under consideration. Feb 1 '15 at 8:22
• This problem admits a straightforward solution using computer algebra techniques. The hypergeometric summand means that Zeilberger's algorithm applies. (Unfortunately I am too busy at this point to write out such a solution.) Feb 3 '15 at 19:22
• When you get the chance, can you please write out a solution or even just provide a link that explains the algorithm you are referring to? Feb 3 '15 at 19:25
• I will try to. Zeilberger's algorithm is implemented in Maple for example. (The sticking point is that Maple's recurrence solving is not strong enough for your particular problem. That means I would need a little more time.) Feb 3 '15 at 19:38
• Thank you very much. If the bounty expires by the time that you get the answer, then I will open up a new bounty for you. Feb 3 '15 at 19:50

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.

• Wow, this looks amazing. I will go verify the logic and if everything works out then I will award you the bounty. Feb 5 '15 at 2:28
• Can you further explain why in the second summation, the bound went from $a+b \leq 2n$ to $a+b \leq n$? Feb 5 '15 at 3:00
• The only problem I am having with this proof is that I am not understanding exactly how/why the bounds become $i \leq n$ and $j \leq n$ when the $i$ and $j$ substitutions are made Feb 5 '15 at 3:04
• The $a+b\leq n$ was a typo. I made an edit to fix that, and I tried to explain why the range of summation (in terms of $i$ and $j$) is $0\leq i,j\leq n$. Feb 5 '15 at 3:13
• Ah it makes sense now. This proof works! Thank you very much! Feb 5 '15 at 3:29

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).

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

• Can you explain how you know that S1 satisfies the same recurrence? Feb 4 '15 at 15:39
• I obtained the $S_1$ recurrence by using computer algebra techniques (omitted because they are unhelpful to a website). It is possible to substitute the sum definition into the recurrence and manipulate. I will try to make that clearer later so that I have not merely re-written the problem if you see it that way! Feb 4 '15 at 15:54
• I have a few questions, What computer algebra system are you using and how are you using it to prove that this statement holds? Feb 4 '15 at 21:59
• Those questions have long answers! I am using a Mathematica package called sigma available by request here and you can find references on how it works. The THEORY is that once you know the recurrence one can substitute in the sum. Here that is harder but I am still optimistic of giving a neat proof. Feb 5 '15 at 9:34