Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I found the following problem while working through Richard Stanley's Bijective Proof Problems (Page 5, Problem 16). It asks for a combinatorial proof of the following: $$ \sum_{i+j+k=n} \binom{i+j}{i}\binom{j+k}{j}\binom{k+i}{k} = \sum_{r=0}^{n} \binom{2r}{r}$$ where $n \ge 0$, and $i,j,k \in \mathbb{N}$, though any proof would work for me.

I also found a similar identity in Concrete Mathematics, which was equivalent to this one, but I could not see how the identity follows from the hint provided in the exercises.

My initial observation was to note that the ordinary generating function of the right hand side is $\displaystyle \frac {1}{1-x} \frac{1}{\sqrt{1-4x}}$, but couldn't think of any way to establish the same generating function for the left hand side.

share|improve this question

1 Answer 1

up vote 6 down vote accepted

Restating your question, you are seeking to find the generating function of the left-hand-side: $$ g(x) = \sum_{n=0}^\infty x^n \sum_{i+j+k=n}\binom{i+j}{i} \binom{j+k}{j} \binom{k+i}{k} = \sum_{i=0}^\infty \sum_{j=0}^\infty \sum_{k=0}^\infty x^{i+j+k} \frac{(i+j)! (i+k)! (j+k)!}{i!^2 j!^2 k!^2} $$ First, carry out summation over $i$: $$ g(x) = \sum_{j=0}^\infty \sum_{k=0}^\infty x^{j+k} \frac{(j+k)!}{j!\cdot k!} {}_2F_1\left(1+j, 1+k; 1; x\right) $$ Now use Euler's transformation ${}_2F_1\left(1+j, 1+k; 1; x\right) = (1-x)^{-j-k-1} \, {}_2F_1\left(-j, -k; 1, x\right)$, which gives $$ g(x) = \frac{1}{1-x} \sum_{j=0}^\infty \sum_{k=0}^\infty \left(\frac{x}{1-x}\right)^{j+k} \frac{(j+k)!}{j!\cdot k!} {}_2F_1\left(-j, -k; 1; x\right) = \\ \frac{1}{1-x} \sum_{j=0}^\infty \sum_{k=0}^\infty \left(\frac{x}{1-x}\right)^{j+k} \frac{(j+k)!}{j!\cdot k!} \sum_{r=0}^{\min(j,k)} \binom{j}{r}\binom{k}{r} x^r = \\ \frac{1}{1-x} \sum_{r=0}^\infty x^r \sum_{j=r}^\infty \sum_{k=r}^\infty \binom{k+j}{k} \binom{j}{r}\binom{k}{r} \left(\frac{x}{1-x}\right)^{j+k} $$ Using $$ \sum_{j=r}^\infty \sum_{k=r}^\infty \binom{k+j}{k} \binom{j}{r}\binom{k}{r} z^{j+k} = \sum_{j=r}^\infty \binom{j}{r} z^{j+r} \sum_{k=0}^\infty \frac{(k+j+r)!}{j! r! k!} z^k =\\ \sum_{j=r}^\infty \binom{j}{r} z^{j+r} \binom{j+r}{j} \sum_{k=0}^\infty \frac{(j+r+1)_k}{k!} z^k = \sum_{j=r}^\infty \binom{j}{r} z^{j+r} \binom{j+r}{j} \left(1-z\right)^{-j-r-1} = \\ \frac{z^{2r}}{(1-z)^{2r+1}} \frac{1}{r!^2} \sum_{j=0}^\infty \frac{(j+2r)!}{j!} \left(\frac{z}{1-z}\right)^j = \frac{z^{2r}}{(1-z)^{2r+1}} \binom{2r}{r} \left(1-\frac{z}{1-z}\right)^{-1-2r} = \binom{2r}{r} z^{2r} \left(1-2z\right)^{-2r-1} $$ we continue: $$ g(x) = \frac{1}{1-x} \sum_{r=0}^\infty x^r \binom{2r}{r} \left(\frac{x}{1-x}\right)^{2r} \left(1 - 2 \frac{x}{1-x} \right)^{-1-2r} = \\ \frac{1}{1-x} \sum_{r=0}^\infty \binom{2r}{r} \frac{1-x}{1-3x} \left(\frac{x^3}{(1-3x)^2}\right)^r = \\ \frac{1}{1-3x} \sum_{r=0}^\infty \binom{2r}{r}\left(\frac{x^3}{(1-3x)^2}\right)^r = \frac{1}{1-3x} \left(1 - 4 \frac{x^3}{(1-3x)^2}\right)^{-1/2} = \frac{1}{1-3x} \left( \frac{(1-4x)(1-x)^2}{(1-3x)^2}\right)^{-1/2} = \frac{1}{1-x} \frac{1}{\sqrt{1-4x}} $$ which is exactly the generating function of the right-hand-side: $$ \sum_{n=0}^\infty x^n \sum_{r=0}^n \binom{2r}{r} \stackrel{n=r+k}{=} \sum_{k=0}^\infty x^r \sum_{r=0}^\infty \binom{2r}{r} x^r = \frac{1}{1-x} \cdot \frac{1}{\sqrt{1-4x}} $$

share|improve this answer
Awesome solution! –  Rijul Saini Jul 31 '12 at 19:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.