Lösung.

Beweis durch Induktion.

Induktionsanfang: $ \mbox{$f(0)=0=2^0-1,\ f(1)=1=2^1-1.$}$

Induktionsschritt: Wir nehmen an, die Formel gilt für alle $ \mbox{$m$}$ mit $ \mbox{$0\leq m<n$}$. Dann gilt:

$ \mbox{$\displaystyle \begin{array}{rcl} f(n)&=&f(n-2)+f(n-1)+2^{n-2}+1\\ &=... ...}-1)+(2^{n-1}-1)+2^{n-2}+1\\ &=&2^{n-1}+2^{n-1}-1\\ &=&2^n-1. \end{array}$}$