prove combinatorical identity using induction

Question

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

Answer 1

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 : https://i.stack.imgur.com/cdIbx.png

Answer 2

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}$

Answer 3

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$.