Induktions-Training

Sei $F_0=0,F_1=1,F_{n+1}=F_n+F_{n-1}$. Beweise für $n\ge1$: $F_n<2^n$.

Beweise für $n\ge0$: $1+2+4+\cdots+2^n=2^{n+1}-1$.

Beweise mit starker Induktion: Jede positive ganze Zahl ist Summe verschiedener Zweierpotenzen.

Eine Lösung zeigt korrekt $P(n)\Rightarrow P(n+1)$ und behauptet danach $P(n)$ für alle $n\ge1$, prüft aber keinen Startfall. Erkläre den Fehler mit einem Beispiel.