Die ersten Werte der Funktion
lauten
. Daraus kann man die Vermutung
ableiten. Wir beweisen diese Formel durch Induktion.
Induktionsanfang:
.
Induktionsschritt: Wir nehmen an, die Formel stimmt für alle
mit
. Wir müssen zeigen, daß sie
auch für
gilt.
Fall
. Hier gilt die Formel, es ist
. (Diesen Fall kann man auch als Teil
des Induktionsanfangs sehen.)
Fall
. Nun haben wir nach Induktion die Gültigkeit der Formel für
und
zur Verfügung.
Wir erhalten