A combinatorial proof of the identity $\sum\limits_{k=0}^n\binom{2k}{k}\binom{2(n-k)}{n-k}=4^n$ I have to prove that $$\sum_{k=0}^n\binom{2k}{k}\binom{2(n-k)}{n-k}=4^n$$ The questions also asks for an algebraic proof and I used induction for that algebraic proof. For a combinatorial proof I have no idea on how to proceed on it . The first thing I thought of using a set and considering $k$ subsets of it but that idea does not work here. I just want a hint and I would prefer not giving out the full answer.
 A: You can prove this identity using paths with steps of size $\pm1$. There are a total of $4^n$ such paths of length $2n$ starting at $(0,0)$. Partition this set of paths according to the final visit to the $x$-axis, call that position $(2k,0).$ 
It is pretty clear that the number of paths from $(0,0)$ to $(2k,0)$ is $2k\choose k$; this is the red part of the diagram. It is not so clear, but 
is true, that the number of paths of length $2n-2k$ that start at $(2k,0)$ and do not touch the $x$-axis is ${2(n-k)\choose n-k}$. This is the black part of the diagram.  


To find a combinatorial argument for this identity has a long history.
See the references below and also Phira's answer here. The following 
diagram fills a gap in my argument above by showing a bijection between
balanced paths that start with an upstep and strictly positive paths. 

Starting with a balanced path, keep the initial upstep, then color red
until you reach the minimum value for the first time. Reverse the red 
section and swap the red and black sections, and connect them 
 to create a strictly positive path.
Starting with a strictly positive path, keep the initial upstep. 
Now the path  ends at $(2n,2a)$ for some $a>0$. Begin at the right and color red 
until you reach level $a$ for the first time.
Reverse the red section and swap the red and black sections, and connect them
 to create a balanced path.
Similarly, balanced paths with an initial downstep are in one-to-one correspondence
with strictly negative paths. Therefore the set of all balanced paths is 
in one-to-one correspondence with paths that don't touch the $x$-axis except at $(0,0)$.


*

*Counting and Recounting: The Aftermath by Marta Sved, 
Math. Intelligencer 6 (1984), no. 4, 44–45.

*Bijections for the identity $4^n=\sum_{k=0}^n {2k\choose k}{2(n-k)\choose n-k}$ by David Callan

*Two New Bijections on Lattice Paths by Glenn Hurlbert and Vikram Kamat,
arXiv:math/0609222 [math.CO]
A: The generating function of the central binomial coefficients is
$$
\sum_{k\ge 0} \binom{2k}{k} x^k = {1\over \sqrt{1-4x}}
$$
Multiplication of this series by itself gives :
$$
\eqalign{
\sum_{k\ge 0} \binom{2k}{k} x^k \cdot \sum_{k\ge 0} \binom{2k}{k} x^k &= {1\over 1-4x} \cr
\sum_{n\ge 0} \biggl( \sum_{k = 0}^n\binom{2k}{k}\binom{2(n-k)}{n-k}\biggr)x^n &= {1\over 1-4x} \cr
}
$$
Therefore the desired sum is the $n^{th}$ coefficient in the expansion of
${1\over 1-4x}$ which is $4^n$. That is :
$$
\sum_{k = 0}^n\binom{2k}{k}\binom{2(n-k)}{n-k} = 4^n
$$
