6
$\begingroup$

Prove that $\sum_{k=0}^n {n \choose k} ^{2} = {2n \choose n}$.

I am trying to prove this by induction. I am having some difficulty after the induction step.

Here is what I have so far:

I start with ${2(m+1) \choose m+1}$ and want to work my way to the summation, with m+1.

Using Pascal's law twice, ${2(m+1) \choose m+1}$= ${2m \choose m-1}$+${2m \choose m}$+${2m \choose m}$+${2m \choose m+1}$= $\sum_{k=0}^m {m \choose k} ^{2}$ +$\sum_{k=0}^m {m \choose k} ^{2}$+${2m \choose m+1}$+${2m \choose m+1}$= 2[$\sum_{k=0}^m {m \choose k} ^{2}$+${2m \choose m+1}]$.

The second equality is by the induction hypothesis. I am not sure what to do about the extra factor of two and if there are any theorems about binomial coefficients that could help.

Thank you!

$\endgroup$
  • $\begingroup$ Probably irrelevant, since you want a proof by induction, but: the equivalent identity $\sum_{k=0}^n \binom nk \binom n{n-k} = \binom{2n}n$ is a convolution identity, which turns out to be easy to prove using the generating function $\sum_{k=0}^\infty \binom nk x^k = (1+x)^n$. $\endgroup$ – Greg Martin Sep 16 '15 at 18:12
  • $\begingroup$ Then would you able to answer the question : math.stackexchange.com/questions/1473827/… ? $\endgroup$ – user230283 Oct 10 '15 at 21:21
2
$\begingroup$

Simpler to prove by induction is Vandermonde's Identity: $$ \sum_{j=0}^k\binom{n}{j}\binom{m}{k-j}=\binom{n+m}{k}\tag{1} $$ For $n=0$, note that the only non-zero term in the sum is when $j=0$. Therefore, the sum is $$ \binom{m}{k}\tag{2} $$ as $(1)$ says. Now, assume that $(1)$ holds for $n$, then compute $$ \begin{align} \sum_{j=0}^k\binom{n+1}{j}\binom{m}{k-j} &=\sum_{j=0}^k\binom{n}{j}\binom{m}{k-j}+\sum_{j=0}^k\binom{n}{j-1}\binom{m}{k-j}\\ &=\sum_{j=0}^k\binom{n}{j}\binom{m}{k-j}+\sum_{j=0}^{k-1}\binom{n}{j}\binom{m}{k-1-j}\\ &=\binom{n+m}{k}+\binom{n+m}{k-1}\\ &=\binom{n+m+1}{k}\tag{3} \end{align} $$ Thus, $(1)$ holds for $n+1$.

Applying $(1)$ to your question yields $$ \begin{align} \sum_{k=0}^n\binom{n}{k}^2 &=\sum_{k=0}^n\binom{n}{k}\binom{n}{n-k}\\ &=\binom{2n}{n}\tag{4} \end{align} $$

$\endgroup$
4
$\begingroup$

Combinatorial Proof

Consider the number of paths in the integer lattice from $(0,0)$ to $(n,n)$ using only single steps of the form: $$(i,j)→(i+1,j)$$ $$(i,j)→(i,j+1)$$

that is, either to the right or up. This process takes $2n$ steps, of which $n$ are steps to the right. Thus the total number of paths through the graph is equal to $\binom{2n}{n}$.

Now let us count the paths through the grid by first counting the paths:

$\qquad$ (1) from $(0,0)$ to $(k,n−k)$

and then the paths:

$\qquad$(2): from $(k,n−k)$ to $(n,n)$.

Note that each of these paths is of length $n$.

Since each path is $n$ steps long, every endpoint will be of the form $(k,n−k)$ for some $k\in\{1,2,\ldots,n\}$, representing $k$ steps right and $n−k$ steps up.

Note that the number of paths through $(k,n−k)$ is equal to $\binom{n}{k}$, since we are free to choose the $k$ steps right in any order. We can also count the number of n-step paths from the point $(k,n−k)$ to $(n,n)$. These paths will be composed of $n−k$ steps to the right and $k$ steps up. Therefore the number of these paths is equal to $\binom{n}{n−k}=\binom{n}{k}$.

Thus the total number of paths from $(0,0)$ to $(n,n)$ that pass through $(k,n−k)$ is equal to the product of the number of possible paths from $(0,0)$ to $(k,n−k)$ i.e. $\binom{n}{k}$, and the number of possible paths from $(k,n−k)$ to $(n,n)$ i.e $\binom{n}{k}$.

So the total number of paths through $(k,n−k)$ is equal to $\binom{n}{k}^2$.

Summing over all possible values of $k=0,\ldots,n$ gives the total number of paths.

Thus we get: $$ \sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n} $$

$\endgroup$
2
$\begingroup$

Here is a proof by counting in two ways. Consider two urns, one with $n$ red balls and another containing $n$ blue balls. The total number of ways to choose $n$ balls (irrespective of color) in all from the two urns is ${2n \choose n}$. Alternatively, $k$ red balls can be chosen from the first urn (in ${n \choose k}$ ways) and for each such $k$-set, $n-k$ blues balls can then be picked from the other urn (in ${n \choose n-k}$ ways). Hence, the total number of ways to pick $n$ balls such that $k$ of them are red is ${n \choose k}{n \choose n-k} = {n \choose k}{n \choose k}$. Summing over $k$, the total number of ways is $\sum_{k=0}^{n}{n \choose k}^{2}$.

$\endgroup$
1
$\begingroup$

Let's see what happens if we consider $$\begin{align*} \binom{n+1}{k}^{\!2} &= \left(\binom{n}{k-1} + \binom{n}{k}\right)^{\!2} \\ &= \binom{n}{k-1}^{\!2} + \binom{n}{k}^{\!2} + 2\binom{n}{k-1}\binom{n}{k}. \end{align*}$$ Now taking the sum from $k = 0$ to $n+1$, observing that $\binom{n}{n+1} = 0$ and $\binom{n}{-1} = 0$, we get $$\sum_{k=0}^{n+1} \binom{n+1}{k}^{\!2} = 2\sum_{k=0}^n \binom{n}{k}^{\!2} + 2\sum_{k=1}^{n} \binom{n}{k-1}\binom{n}{k}.$$ We now wish to show the second sum on the RHS is $\binom{2n}{n+1}$. But this is a special case of Vandermonde's convolution/identity $$\sum_x \binom{r}{a+x}\binom{s}{b-x} = \binom{r+s}{a+b}, \quad a, b \in \mathbb Z,$$ where $r = s = b = 1$ and $a = -1$. The rest follows by induction from the calculations you previously established.

But here's the funny thing: the original identity is itself a special case of Vandermonde's, with the choice $r = s = n$, $x = k$, $a = 0$, $b = n$, since $\binom{n}{n-k} = \binom{n}{k}$. Here's another approach: Inductive Proof for Vandermonde's Identity?

$\endgroup$
1
$\begingroup$

I know you want an induction proof to this but I can't resist giving you a combinatorial one. The right side is the answer to the question: "In how many ways can I draw $n$ element from a $2n$ element set" - it's obviously ${2n\choose n}$

To get the right side lets divide our $2n$ set into two n-element subsets, and lets draw $k$ elements from the first one and $n-k$ elements from the second one. There are ${n\choose k}{n\choose n-k}={n\choose k}{n\choose k}={n\choose k}^2$ ways to do it. We can do it for every k from 1 up to n and the sum gives us the total numer of ways to choose n elements from a 2n set, therefore: $$\sum_{k=0}^n {n \choose k} ^{2} = {2n \choose n}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.