Show $\sum_{k=0}^{n} \binom{2k}{k} \binom{2(n-k)}{n-k} = 4^n$.

Question

For $n\ge 0$, show $\sum_{k=0}^{n} \binom{2k}{k} \binom{2(n-k)}{n-k} = 4^n$.

Want to first clarify the logic of the problem.

It is not only having variable $k$ (in number of items to be chosen in each category) as variable, but also having the quantity available in each category as variable.

I mean if instead of taking variable quantity : $2k, 2(n-k)$, have fixed qty. (say, $x,y$), then can define a problem as choosing a total of $k$ items from two categories having fixed quantities $x,y$.

But, now the two input quantities are variable and this makes it difficult to find a problem that can be represented by the equality.

---

Now, try to prove it using MI.

Over a well ordered set of non-negative integers, induction can be used.

Base case: $n=0$
$\binom{0}{0} \binom{0}{0} = 1$.

Taking the rhs, get : $4^0= 1$.

Induction hypothesis: it is true for natural number $n$.

So, $\sum_{k=0}^{n} \binom{2k}{k} \binom{2(n-k)}{n-k} = 4^n$

Inductive step: need show for next natural $n+1$

$\sum_{k=0}^{n+1} \binom{2k}{k} \binom{2(n+1-k)}{n+1-k} = 4^{n+1}$

This should lead to :

$4^n + \binom{2(n+1)}{(n+1)} \binom{2((n+1)-(n+1))}{((n+1)-(n+1))}= 4^{n+1}$

$\implies \binom{2(n+1)}{(n+1)} = 4^{n}.(3)$

Please help to proceed further, or suggest alternative approach.

Answer 1

Take squares on both sides of the expansion $$(1-4x)^{-1/2}=\sum_{n=0}^{\infty}{2n \choose n}x^n.$$