Summe/Teilmengenanzahl/Induktion/Aufgabe/Lösung

Für $n = 0$ steht beidseitig $1$ . Es sei die Aussage für $n$ bekannt. Dann ist unter Verwendung von Fakt und der Induktionsvoraussetzung

\begin{matrix} \sum_{j = 0}^{n + 1} (\binom{n + 1}{j}) 2^{j} & = \sum_{j = 0}^{n + 1} ((\binom{n}{j}) + (\binom{n}{j - 1})) 2^{j} \\ = \sum_{j = 0}^{n + 1} (\binom{n}{j}) 2^{j} + \sum_{j = 0}^{n + 1} (\binom{n}{j - 1}) 2^{j} \\ = 3^{n} + \sum_{k = 0}^{n} (\binom{n}{k}) 2^{k + 1} \\ = 3^{n} + 2 \sum_{k = 0}^{n} (\binom{n}{k}) 2^{k} \\ = 3^{n} + 2 \cdot 3^{n} \\ = 3^{n + 1} . \end{matrix}