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

${\displaystyle {}{\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}}}$