Showing classic combinatorial $4^n$ identity using Vandermonde - What goes wrong? [duplicate]

Solution 1:

We have to avoid $k$ in the top argument when using Vandermonde. (See counterexample below.)

Hence if we do, then
$$ \sum_{k = 0}^n \binom{2k}{k} \binom{2(n - k)}{n - k} = \sum_{k = 0}^n (-4)^k \binom{-1/2}{k} (-4)^{n - k} \binom{-1/2}{n - k} = (-4)^n \sum_{k = 0}^n \binom{-1/2}{k} \binom{-1/2}{n - k},$$ we get, from Vandermonde, $$ \sum_{k = 0}^n \binom{2k}{k} \binom{2(n - k)}{n - k}= (-4)^n \binom{-1}{n} = (-4)^n (-1)^n = 4^n. $$

Note on having $k$ in the top argument: consider the trivial example $$ \sum_{k = 0}^n \binom{k}{k} \binom{n - k}{n - k} = n + 1; $$ attempting to apply Vandermonde here would suggest it is equal to $\binom{n}{n} = 1$.