Aufgabe:
Sie gehen eine Treppe mit n Stufen hinauf. Dabei können Sie jede Stufe entweder betreten oder übertreten
und die nachfolgende betreten. Die letzte Stufe müssen Sie betreten. Sei an die Anzahl Möglichkeiten, auf
wie viele Arten Sie die Treppe hinaufsteigen können
i) Geben Sie ai
ai = 1, . . . , 4 an.
ii) Finden und begründen Sie einen rekursiven Ausdruck für a n+1.
Problem/Ansatz:
Nach meinem Ansatz haben wir:
n=1 Eine Möglichkeit
n=2 Zwei Möglichkeiten, also beide Stufen betreten und die Erste überspringen und die zweite betreten
n=3 Drei Möglichkeiten, also alle drei Stufen betreten, die erste überspringen und die zweite und dritte betreten, die erste betreten und die zweite überspringen und letzte betreten
n=4 5 Möglichkeiten, alle 4 Betreten & Erste betreten zweite überspringen und 3 / 4 betreten & erste überspringen und 2 / 3 / 4 betreten & 1 / 2 betreten 3 überspringen, 4 betreten & 1 überspringen 2 betreten 3 überspringen 4 springen
Soweit fine. also Rekursiv Ausdruck: an+1 = an + an-1
Aber wie führe ich jetzt meinen Beweis für diesen Ausdruck?
Mein Ansatz wäre:
1 Fall: Wir überspringen die erste Stufe nicht, also wir betreten die n+1 Stufe, dann haben wir an Möglichkeiten
2 Fall: Wir überspringen die erste Stufe, also sind wir gezwungen die zweite Stufe (n+1 und n) betreten also nur noch an-1 Möglichkeiten
q.e.d
Wäre mein Beweis für die Rekursivedartellung korrekt?
