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