My teacher showed us a proof by induction for this equation for $n\in\mathbb{N}$:
$$\sum\limits_{k=0}^n{{n}\choose{k}} = 2^n$$
In the first step, this sum is rewritten using ${{n+1}\choose{k}}={{n}\choose{k-1}}+{{n}\choose{k}}$.
However, he doesn't explain why this would be - and since he just introduced binomials coefficients, I assume it's something trivial, which I just don't see. I can't figure out why this would hold though.
I tried rewriting the binomial coefficients with ${{n}\choose{k}}=\frac{n!}{k!\cdot(n-k)!}$ when $n,k\in\mathbb{N}$ and $n\geq k$:
$${{n+1}\choose{k}}=\frac{(n+1)!}{k!\cdot(n+1-k)!}$$
$${{n}\choose{k-1}}=\frac{n!}{(k-1)!\cdot(n-k+1)!}$$
$${{n}\choose{k}}=\frac{n!}{k!\cdot(n-k)!}$$
But I can't prove:
$$\frac{(n+1)!}{k!\cdot(n+1-k)!} \stackrel{?}{=} \frac{n!}{(k-1)!\cdot(n-k+1)!} + \frac{n!}{k!\cdot(n-k)!}$$
Am I on the right track? Is there a basic idea behind this equation which makes you see it easily?