Binomialkoeffizient/Summe/Induktion/Aufgabe/Lösung

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

\begin{matrix} 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} ((\binom{n}{k - 1}) + (\binom{n}{k})) + 1 \\ = \sum_{k = 1}^{n + 1} (\binom{n + 1}{k}) + 1 \\ = \sum_{k = 0}^{n + 1} (\binom{n + 1}{k}) . \end{matrix}

Zur gelösten Aufgabe