Binomialkoeffizient/Summe/Induktion/Aufgabe/Lösung

Für ${}n=0$ steht einerseits ${}2^{0}=1$ und andererseits ${}1^{0}\cdot 1^{0}=1$. Sei die Aussage bereits für ${}n$ bewiesen. Dann ist unter Verwendung der Induktionsvoraussetzung und von Fakt

${}{\begin{aligned}2^{n+1}&=2\cdot 2^{n}\\&=(1+1)\sum _{k=0}^{n}{\binom {n}{k}}\\&=\sum _{k=0}^{n}{\binom {n}{k}}+\sum _{k=0}^{n}{\binom {n}{k}}\\&=\sum _{k=1}^{n+1}{\binom {n}{k-1}}+\sum _{k=0}^{n+1}{\binom {n}{k}}\\&=\sum _{k=1}^{n+1}\left({\binom {n}{k-1}}+{\binom {n}{k}}\right)+1\\&=\sum _{k=1}^{n+1}{\binom {n+1}{k}}+1\\&=\sum _{k=0}^{n+1}{\binom {n+1}{k}}.\end{aligned}}$

Zur gelösten Aufgabe