I have tried using the principle of mathematical induction. The base case is simple, but I am having trouble with the induction step. Any help would be great, thanks !
[Math] Proving $\sum_{k=0}^n {n \choose k}{m-n \choose n-k} = {m \choose n}$
combinationscombinatorics
Related Solutions
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} $$
Consider the following "more conventional" statement (adjust notation accordingly) of the problem:
Problem: Show that for each $n\geq 0$, $$ \sum_{i=0}^n\binom{m+i}{i}=\binom{m+n+1}{n}. $$
Proof: For each $n\geq 0$, let $S(n)$ be the declaration that for every $m\geq 0$, $$ \sum_{i=0}^n\binom{m+i}{i}=\binom{m+n+1}{n}. $$
Base step: $S(0)$ says that $\sum_{i=0}^0\binom{m+i}{i}=\binom{m+1}{0}$, which is true because both sides are equal to $1$.
Induction step: For some $k\geq 0$, assume that $S(k)$ is true. To be shown is that $S(k+1)$ is true; that is, for any $m\geq 0$, $$ \sum_{i=0}^{k+1}\binom{m+i}{i}=\binom{m+k+2}{k+1}. $$ Beginning with the LHS, \begin{align} \sum_{i=0}^{k+1}\binom{m+i}{i} &= \sum_{i=0}^k\binom{m+i}{i}+\binom{m+k+1}{k+1}\tag{defn. of $\sum$}\\[1em] &= \binom{m+k+1}{k}+\binom{m+k+1}{k+1}\tag{by $S(k)$}\\[1em] &= \binom{m+k+2}{k+1},\tag{Pascal's identity} \end{align} we obtain the RHS.
By mathematical induction, then, for all $n\geq 0, S(n)$ is true. $\Box$
Best Answer
Although a MI method may be used, a Combinatorial argument is much more simple. We assume that we want to select n distinct objects of a total of m objects. We can always select them directly and get RHS.Alternatively, we can separate the m objects into two groups, one of n and the other of m-n.
Now assume we take 0 from the group with n, we must choose n from the group with m-n. If we take 1 from the group with n, we must Take (n-1) from the group with (m-n). We continue repeating this & sum up the result, and we get RHS.