Rekursion bestimmen

Neue Frage »

Peter430 Auf diesen Beitrag antworten »
Rekursion bestimmen
Man bestimme die Anzahl der 0-1 Zahlenfolgen der Länge n. Es dürfen aber keine zwei benachbarten Zahlen 0 sein. Das Ganze soll über eine rekursive Formel für die Anzahl a_n gelöst werden.

Aus n Zahlen ziehe ich i-mal eine 0. Die nicht gezogenen Zahlen sind 1. Bekanntermaßen ist die Anzahl der Möglichkeiten dafür (n + 1 - i) über i. Und wenn ich über alle i summiere erhalte ich die Anzahl a_n der möglichen 0-1 Zahlenfolgen der Länge n ohne Doppelnull. Damit erhalte ich:

a_1 = 1 + 1 = 2
a_2 = 1 + 2 = 3
a_3 = 1 + 3 + 1 = 5
a_4 = 1 + 4 + 3 = 8
a_5 = 1 + 5 + 6 + 1 = 13
a_6 = 1 + 6 + 10 + 4 = 21
a_7 = 1 + 7 + 15 + 10 +1 = 34

Das sieht mir sehr nach den Fibonacci Zahlen aus.

Natürlich könnte man das mit Induktion beweisen. Aber kann man sich das denn nicht auch irgenwie veranschaulichen ? Wenn ich die Länge der 0-1 Zahlenfolgen um 1 erhöhe, warum wird dann gerade die Anzahl der beiden Vorgänger aufaddiert ?
HAL 9000 Auf diesen Beitrag antworten »

Man kann sich leicht inhaltlich überlegen, warum die Fibonacci-Rekursion hier gilt. Mach bei den -stelligen Zahlen die Fallunterscheidung nach der letzten Ziffer:

a) Ist diese eine 1, dann gibt es für die Ziffern davor nur die Einschränkung, dass keine zwei Nullen hintereinander vorkommen dürfen. Die Anzahl solcher -stelligen Zahlen ist ja nun gerade , und an jeder dieser Zahlen hängen wir Ziffer 1 dran.

b) Ist diese eine 0, dann darf die vorletzte Ziffer keine 0 sein, d.h., die Zahl muss auf 10 enden. Für die Ziffern davor gibt es wieder nur die Einschränkung, dass keine zwei Nullen hintereinander vorkommen dürfen. Die Anzahl solcher -stelligen Zahlen ist , und an jede dieser Zahlen hängen wir die zwei Ziffern 10 dran.

Macht summa summarum . Fehlen noch die Anfangswerte (0/1) und (01/10/11), schon haben wir die verschobene Fibonaccifolge .
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »