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{aligned}\sum _{j=0}^{n+1}{\binom {n+1}{j}}2^{j}&=\sum _{j=0}^{n+1}{\left({\binom {n}{j}}+{\binom {n}{j-1}}\right)}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{aligned}}