Let $r, n ∈ N$ and let $r ≤ n$. Give an inductive proof for:
$$ {n+1 \choose r + 1} = ∑_{k=r}^n {k \choose r} $$
Step 1: We will prove this using induction on n. n = 1
Step 2: n = k, prove for n = 1.
Am I on the right track? Not sure where to go from there though
The identity you are trying to prove is known as the "Hockey Stick Identity".
The base case should be n = r and not n = 1.
Base Case: n = r
$$\sum^{n}_{k=r}\binom{k}{r}= \sum^{r}_{k=r}\binom{k}{r}= \binom{r}{r}=1=\binom{r+1}{r+1}$$
Inductive Hypothesis:
Assume $$\sum^{n}_{k=r}\binom{k}{r}=\binom{n+1}{r+1}$$ is true for some $n \ge r$.
Inductive Step: n + 1
$$\sum^{n+1}_{k=r}\binom{k}{r}= \sum^{n}_{k=r}\binom{k}{r} + \binom{n+1}{r} $$
$$=\binom{n+1}{r+1} + \binom{n+1}{r}\quad\quad$$
$$=\binom{n+2}{r+1}$$