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.
Best Answer
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}} $$