proving that $\sum_{k=0}^{n}{{n \choose k}{n+k \choose k}}=\sum_{k=0}^{n}{2^k{n \choose k}^2}$

Question

proving that $$\sum_{k=0}^{n}{{n \choose k}{n+k \choose k}}=\sum_{k=0}^{n}{2^k{n \choose k}^2}$$

(prove can be combi or algebraic)

Answer 1

Suppose that I have $n$ white balls in Box A and $n$ red balls in Box B. I pick some of the white balls, paint them blue, and transfer them to Box B. I then transfer exactly enough balls from Box B to Box A to leave each box containing $n$ balls again.

Suppose that I initially transfer $k$ balls from Box A to Box B; they can be chosen in $\binom{n}k$ ways. There are then $\binom{n+k}k$ ways to choose the $k$ balls to be transferred from Box B to Box A to bring each box to $n$ balls, so there are $\binom{n}k\binom{n+k}k$ possible outcomes in which $k$ balls are transferred at each step. Summing over $k$, we see that there are altogether $\sum_{k=0}^n\binom{n}k\binom{n+k}k$ possible outcomes, distinguishable by the numbers of red and blue balls that end up in Box A.

Alternatively, for some $k$ we could trade $k$ balls from Box A for $k$ from Box B, so that we now have $n-k$ white and $k$ red balls in Box A. We could then pick any subset of the $k$ red balls in Box A and paint them blue. This procedure yields exactly the same set of outcomes as the first procedure and can clearly be carried out in $\sum_{k=0}^n2^k\binom{n}k^2$ different ways: there are $\binom{n}k$ ways to choose the $k$ balls to be transferred from Box A to Box B, $\binom{n}k$ ways to choose the balls to be transferred from Box B to Box A, and $2^k$ ways to decide which of the latter are to be painted blue. This establishes the identity.

Answer 2

We may start by considering the central Delannoy numbers, i.e. the number of paths in a $n\times n$ grid which go from the bottom-left corner to the upper-right corner through moves in the East, North and North-East direction.

The combinatorial definition gives $$ D(n)=[x^n y^n]\frac{1}{1-x-y-xy}=[x^n y^n]\frac{1}{2-(1+x)(1+y)} $$ so $$ D(n)=[x^n y^n]\sum_{m\geq 0}\frac{(1+x)^m (1+y)^m}{2^{m+1}}=\sum_{m\geq n}\frac{1}{2^{m+1}}\binom{m}{n}^2.$$ On the other hand these paths can be counted according to the number of diagonal moves appearing in them. Assuming there are $k$ diagonal moves, we have $n-k$ horizontal moves and $n-k$ verticas moves. These moves can be performed in any order, so the number of paths with $k$ diagonal moves is given by the multinomial coefficient $\binom{2n-k}{k,n-k,n-k}=\binom{2n-k}{n}\binom{n}{k}$ and $$ D(n) = \sum_{k=0}^{n}\binom{n}{k}\binom{2n-k}{n-k} = \sum_{m=0}^{n}\binom{n}{m}\binom{n+m}{m}=P_n(3)$$ where $P_n$ is a Legendre polynomial. Indeed Rodrigues' formula for standard and shifted Legendre polynomials leads to the explicit representations

$$ P_n(x)=\frac{1}{2^n}\sum_{k=0}^{n}\binom{n}{k}^2(x-1)^k(x+1)^{n-k} $$ $$ P_n(2x+1) = \sum_{k=0}^{n}\binom{n}{k}\binom{n+k}{k}x^k $$ and this shows

$$ \sum_{m=0}^{n}\binom{n}{m}\binom{n+m}{m}=\sum_{m=0}^{n}2^m\binom{n}{m}^2=\sum_{m\geq n}\frac{1}{2^{m+1}}\binom{m}{n}^2. $$

From the generating function of the central Delannoy numbers it is not difficult to derive the following integral representation which is pretty useful for approximations and asymptotics:

$$ D(n)=\frac{1}{2\pi}\int_{0}^{2\pi}\frac{d\theta}{\left(3-2\sqrt{2}\cos\theta\right)^{n+1}}.$$