Using induction prove $\sum\limits_{k=1}^n\binom{k}{k-1}=\binom{n+1}{n-1}$

Question

$\sum\limits_{k=1}^n\binom{k}{k-1}=\binom{n+1}{n-1}$

We are supposed to use induction to prove this inequality. After the base case, I tried to use the definition $\binom{n}{k} = \frac{n!}{k!(n-k)!}$. But the results were convoluted and did not lead to a satisfactory proof.

A guide through the inductive steps would be helpful.

Answer 1

Hint

$$\binom{n+1}{n-1} = \frac{(n + 1)!}{(n + 1)! \ 2!} = \frac{1}{2}n(n + 1) $$

(Which is the sum of the first $n$ numbers)

Answer 2

Let $n=m$. Then assume $$\sum_{k=1}^m\binom{k}{k-1}=\binom{m+1}{m-1}$$ Now for $n=m+1$ $$\sum_{k=1}^{m+1}\binom{k}{k-1}=\binom{m+1}{m-1}+\binom{m+1}{m}=\binom{m+2}{m}$$ It shouldn't be hard to show the last step above. But this is the induction step that you were looking for.