Beispiel.

Sei $ \mbox{$f:\mathbb{N}\longrightarrow \mathbb{R}$}$ rekursiv definiert durch die Anfangswerte $ \mbox{$f(0) = 0$}$, $ \mbox{$f(1) = 1$}$, und durch die Rekursionsgleichung

$ \mbox{$\displaystyle f(n) \; =\; f(n-2) + f(n-1) + 2^{n-2} + 1\; . $}$
Zeige: $ \mbox{$f(n) = 2^n - 1$}$ für alle $ \mbox{$n$}$.