Let $0 \leq m \leq n$ be integers. Prove the following formula:
${n \choose m} + {n-1\choose m} +{n-2\choose m}+...+{m\choose m} = {n+1\choose m+1}$
Hint: Use induction on n and Pascal's Identity.
By Pascal the first two terms can be substituted by ${n \choose m} + {n-1\choose m} = - {n-1\choose m-1}$ Honestly not sure where I am supposed to be going with this.
As with all inductions, we start with a base case:
Suppose $n=0$ does $0 \choose m$ = $0+1 \choose m+1$. Well here, if $n=0$ then $m=0$ and this holds easily $0 \choose 0$ = $1 \choose 1$ =1.
So now suppose the hypothesis, that $n \choose m$ + ... + $ m\choose m$=$n+1 \choose m+1$ is it true that the same holds for $n+1$? Does $n+1 \choose m$ + $n \choose m$ + ... + $m\choose m$=$n+2 \choose m+1$.
We can use Pascals identity for the right hand side, to reduce $n+2 \choose m+1$ to $n+1 \choose m$ + $n+1 \choose m+1$. Putting this in, we get:
$n+1 \choose m$ + $n \choose m$ + ... + $m\choose m$= $n+1 \choose m$ + $n+1 \choose m+1$.
This equality obviously holds if the hypothesis does (since we added $n+1 \choose m$ to both sides) and since it holds $n=0$ we can conclude it holds for all natural numbers $n$.