TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen WS13/Beispiel 253

Stellen Sie eine Rekursion für die gesuchten Zahlen $a_{n}$ auf und lösen Sie diese:

Eine Münze werde so oft geworfen, bis man zweimal hintereinander das Ergebnis "Kopf" erhält. Auf diese Art erhält man eine Folge, deren Glieder entweder Kopf oder Zahl sind.

$a_{n}$ bezeichne die Anzahl der möglichen Folgen der Länge $n$.

Lösungsvorschlag von Berti

K bezeichnet Kopf, Z bezeichnet Zahl, sobald also zwei KK hintereinander kommen, ist die Folge zuende. Das heißt auch, dass KKK nie auftreten kann. Das heißt, dass bei $n>=3$ am Ende immer ZKK stehen muss:

2 Stellen ($x(2)=1$):

• KK

3 Stellen ($x(3)=1$):

• ZKK

4 Stellen ($x(4)=2$):

• ZZKK
• KZKK

5 Stellen ($x(5)=3$):

• ZZZKK
• ZKZKK
• KZZKK

6 Stellen ($x(6)=5$):

• ZZZZKK
• ZZKZKK
• ZKZZKK
• KZZZKK
• KZKZKK

Man sieht also, dass man den Nachfolger immer folgendermaßen bilden kann: Man nimmt alle Elemente des Vorgängers und fügt ein Z vorne an. Bei den Elementen, bei denen bereits ein Z steht, hängt man außerdem noch ein K vorne an. Dadurch erhält man alle gültigen Kombinationen.

Wie man auch relativ schnell erllkennt, lässt sich die Rekursion folgendermaßen ausdrücken: $x_{n}=x_{n-2}+x_{n-1}$

Diese Gleichung wurde bereits mehrmals gelöst, z.B. hier und deshalb werde ich auf eine weitere Lösung jetzt nicht mehr näher eingehen. Wichtig ist noch, dass die Anfangswerte bei diesem Beispiel allerdings anders sind, d.h. dass $C_{1}$ und $C_{2}$ hier andere Werte annehmen.

-- Berti933 (Diskussion) 20:44, 21. Jan. 2015 (CET)