# Proof of $\sum_{k=1}^n \binom{n}{k} \binom{n}{n+1-k} = \binom{2n}{n+1}$ via induction

I'm having trouble to prove the following formula using Induction on $n \in \mathbb{N}$: $$\sum_{k=1}^n \binom{n}{k} \binom{n}{n+1-k} = \binom{2n}{n+1}.$$ I've tried all the usual identities, but they seem to lead nowhere. Is there any trick to this, or is it just not possible to prove this using induction?

I'm thankful for any tip or advice on how to approach this :)

Select $n+1$ unit squares from a $2\times n$ rectangle. What do you see?

• Is that a hint to an inductive proof? Commented Dec 12, 2017 at 16:40
• Actually you don't even need induction. The picture say it all. Select any $(n+1)$-subset of $\{0,1\}\times\{1,\dots,n\}$. You see a $k$-subset of the fist column and, independent of it, a $(n+1-k)$-subset of the other column. This exactly represents the LHS. Commented Dec 12, 2017 at 17:22
• Your suggestion leads to what I consider the "right" proof, the "natural" proof. (And it proves a more general result, about $\binom{2n}{m}$ for arbitrary $m$.) But the question specifically asked for a proof by induction on $n$. That seems to make the problem harder. Commented Dec 12, 2017 at 18:08

As already noted yours is just a Vandermonde convolution, which is normally proved by taking the product of two binomials.

However, if we limit to consider the general Vandermonde convolution with non-negative integer parameters, except at most one of the upper parametr which may also be real, i.e. $$\sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,m} \right)} {\left( \matrix{ m \cr k \cr} \right)\left( \matrix{ r \cr n - k \cr} \right)} = \left( \matrix{ r + m \cr n \cr} \right)\quad \left| \matrix{ \;0 \le m,n \in Z \hfill \cr \;r \in R \hfill \cr} \right.$$ then the convolution can be obtained as the $m$ times iteration of the basic recursive identity \eqalign{ & \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,m} \right)} {\left( \matrix{ m \cr k \cr} \right)\left( \matrix{ r \cr n - k \cr} \right)} = \left( \matrix{ r + m \cr n \cr} \right)\quad \left| \matrix{ \;0 \le m,n \in Z \hfill \cr \;r \in R \hfill \cr} \right. \cr & \left( \matrix{ r + m \cr n \cr} \right) = \left( \matrix{ r + m - 1 \cr n \cr} \right) + \left( \matrix{ r + m - 1 \cr n - 1 \cr} \right) = \left( \matrix{ 1 \cr 0 \cr} \right)\left( \matrix{ r + m - 1 \cr n \cr} \right) + \left( \matrix{ 1 \cr 1 \cr} \right)\left( \matrix{ r + m - 1 \cr n - 1 \cr} \right) = \cr & = \left( \matrix{ r + m - 2 \cr n \cr} \right) + \left( \matrix{ r + m - 2 \cr n - 1 \cr} \right) + \left( \matrix{ r + m - 2 \cr n - 1 \cr} \right) + \left( \matrix{ r + m - 2 \cr n - 2 \cr} \right) = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,2} \right)} {\left( \matrix{ 2 \cr k \cr} \right)\left( \matrix{ r + m - 2 \cr n - k \cr} \right)} = \cr & = \quad \cdots = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,m} \right)} {\left( \matrix{ m \cr k \cr} \right)\left( \matrix{ r \cr n - k \cr} \right)} \cr}

Now, the basic recursive identity can be taken as just the definition of the binomial , or if the binomial is defined in other ways it can be easily demonstrated also by induction.

And once you have demonstrated the basic recursion, its iteration leads you to demonstrate the Vandermonde convolution.