Ich habe einen Fibonaci-Baum Fn der zu den Knoten Fn-1 und Fn-2 mit der Wahrscheinlichkeit p = 1/2 führt (zufällige Auswahl des Wegs). Es sind außerdem F1 und F0 Blätter. Ich soll zeigen, dass die Wahrscheinlichkeit, vom Wurzelknoten Fn zu einem F1 Blatt zu kommen,
2/3 * (1 - (-1/2)^n)
entspricht.
Ich bin hier recht überfragt, wie man auf so eine Lösung kommt. Ich kann nur für einfache Fälle wie n = 3 meinen eigenen Lösungsweg manuell aufzeigen:
Bei F3 gibt es einen Teilbaum F2 und F1. F1 ist schonmal mit der Wahrscheinlichkeit p = 1/2 erreichbar. um von F3 über F2 auf F1 zu kommen, muss ich zwei mal mit der Wahrscheinlichkeit 1/2 "den Weg entlanglaufen". Somit ergibt sich für F3 also die Gesamtwahrscheinlichkeit
1/2 + (1/2)^2 = 3/4
Zur Selbstkontrolle mit der gegebenen Formel:
2/3 * (1 - (-1/2)^3) = 2/3 * 9/8 = 18/24 = 3/4
Hat jemand einen Tipp wie ich das angehen sollte?
