Prove by mathematical induction for all natural numbers $n$:
$$\sum_{k=0}^{n} \binom{n}{k}=2^n$$
thus is it sufficient to show that (but I think I made a mistake) thus how to do it properly?
$$2^n+\binom{n+1}{n+1}=2^{n+1}$$
[Math] Induction proof: sum of binomial coefficients
binomial-coefficientsinduction
Best Answer
Not quite, because ${n+1\choose n+1}=1$. Combinatorically, is it easy to see that ${n+1\choose k}={n\choose k}+{n\choose k-1}$ (we either include the last element or we don't). From here on the proof is easy because (using the induction hypothesis):
$\sum_{k=0}^{n+1} {n+1\choose k}=\sum_{k=0}^{n+1} {n\choose k}+{n\choose k-1}=\sum_{k=0}^{n+1} {n\choose k}+\sum_{k=0}^{n+1} {n\choose k-1}=2^n+2^n=2^{n+1}$
Because ${n\choose -1}={n\choose n+1}=0$ (it's impossible to choose -1 or n+1 elements out of n).