prove combinatorical identity using induction Question:
prove by induction on $n+m$ the combinatoric identity:
$$\sum_{k = 0}^n {m + k \choose k} = {m + n + 1 \choose n}$$
I've tried to do on both $n$ and $m$ but I think it isn't the right way.
Thanks
 A: Actually only an induction on n is required :
The case $n=1$ is trivial : ${m \choose 0} + {m \choose 1} = m + 1 = {m + 1 \choose 1}$
Assuming $n>1$. 
$$\sum_{k = 0}^{n+1} {m + k \choose k} = \sum_{k = 0}^n {m + k \choose k} + {m + n + 1 \choose n+1}$$
Then you use the induction property on the first term of the right part.
$$\sum_{k = 0}^{n+1} {m + k \choose k} = {m + n + 1 \choose n} + {m + n + 1 \choose n+1}$$
Finally you use the fact that :
$$ {n \choose k} + {n \choose k+1} = {n+1 \choose k+1}$$
The proof (not very pretty, but effective) of this last property can be found here : http://i.imgur.com/4uSnP6V.png
A: In order to perform induction on $m+n$, let us define $p$ such that $p=m+n$.
For $p=1$, we have two cases $m=0,n=1$ or $m=1,n=0$
For $m=0,n=1$, we have
${0 \choose 0}+{1 \choose 1}=2={2 \choose 1}$
For $m=1,n=0$, we have
${1 \choose 0}={2 \choose 0}$
For $p>1$, by induction we have
$\large \sum_{k=0}^{p-m}{m+k \choose k}={p+1 \choose p-m}$
So that 
$\large \sum_{k=0}^{p-m+1}{m+k \choose k}=\sum_{k=0}^{p-m}{m+k \choose k}+{p-m+1+m \choose p-m+1}={p+1 \choose p-m}+{p-m+1+m \choose p-m+1}$
$\large=\frac{(p+1)!}{(p-m)!(m+1)!}+\frac{(p+1)!}{(p-m+1)!m!}=\frac{(p+1)!(m+1+p-m+1)}{(m+1)!(p-m+1)!}=\frac{(p+2)!}{(m+1)!(p-m+1)!}$
$\large ={p+2 \choose p-m+1}={(p+1)+1 \choose (p+1)-m}$
A: Another take.
$m=0$:
$$\sum_{k=0}^n\binom kk=\sum_{k=0}^n 1=n+1=\binom{n+1}1=\binom{n+1}n.$$
$n=0$:
$$\sum_{k=0}^n\binom kk=\binom00=1=\binom{m+1}0
.$$
$m,n>0$:
\begin{align*}
\sum_{k=0}^n\binom{m+k}k&=
1+\sum_{k=1}^n\left(\binom{m-1+k}k+\binom{m-1+k}{k-1}\right)
\\&=\sum_{k=0}^n\binom{m-1+k}{k}+\sum_{k=0}^{n-1}\binom{m+k}{k}
\\&=\binom{m+n}n+\binom{m+n}{n-1}=\binom{m+n+1}n
\end{align*}
The next to last equality uses induction on $n+m$.
