Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Fibonacci Induktion

Fibonacci Induktion

Schüler Gymnasium,

Tags: Fibonacci, Folgen, Induktion, Zahl

Noritz aktiv_icon

22:16 Uhr, 07.12.2016

Hallo,

Ich muss folgende Behauptung per vollständiger Induktion beweisen und komme leider nicht weiter.

F_{n + 10} = F_{n - 2} * F_{10} + F_{n - 1} * F_{11}

Hierbei ist zu erwähnen, dass bei uns die Fibonacci Folge etwas "verschoben" ist.
Somit gilt:

F_{0} = F_{1} = 1

Außerdem soll n > 1 sein.

Meine Überlegungen waren bis jetzt folgende:

Induktionsanfang:

F_{n + 10} = F_{n - 2} * F_{10} + F_{n - 1} * F_{11}

F_{12} = 1 * F_{10} + 1 * F_{11}

Induktionsvoraussetzung:

n = k; F_{k + 10} = F_{k - 2} * F_{10} + F_{k - 1} * F_{11}

Induktionsbehauptung:

n = k + 1; F_{k + 11} = F_{k - 1} * F_{10} + F_{k} * F_{11}

Induktionsbeweis:
Hierbei habe ich echt meine Probleme. Ich weiß einfach nicht wie ich ansetzten soll.
Ich habe bereitsversucht, den linken Teil zu zerlegen(Mit der Definition von F), den rechten Teil zu zerlegen und umzuformen, jedoch leider ohne Erfolg.
Das was mich so behindert ist die Rekursionsformel.
Vielleicht habt ihr ja Ideen wie es lösbarer wird.

Danke!

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Werner-Salomon aktiv_icon

00:30 Uhr, 08.12.2016

Hallo,
letztlich soll im sogenannten Induktionsschritt gezeigt werden, dass

F_{n + 11}

auch die obige Gleichung erfüllt. Die Rekursion lautet doch

F_{n + 1} = F_{n} + F_{n - 1}

bzw.

F_{n + 11} = F_{n + 10} + F_{n + 9}

dort setzte ich die vorgegebene Gleichung ein:

F_{n + 11} = F_{n - 2} \cdot F_{10} + F_{n - 1} \cdot F_{11} + F_{n - 3} \cdot F_{10} + F_{n - 2} \cdot F_{11} = (F_{n - 2} + F_{n - 3}) \cdot F_{10} + (F_{n - 1} + F_{n - 2}) \cdot F_{11}

= F_{n - 1} \cdot F_{10} + F_{n} \cdot F_{11}

d.h. wenn es für

n + 10

gilt, so gilt es auch für

n + 11

- q.e.d.

Gruß
Werner

Noritz aktiv_icon

10:13 Uhr, 08.12.2016

Danke schon einmal für die Antwort!
Ich habe bis jetzt verstanden, dass du

F_{n + 11}

nach der Fibonacci Definition zu

F_{n + 10} + F_{n + 9}

umgeformt hast.

So wie ich das verstehe hast du dann in

F_{n + 10}

die Induktionsvorraussetzung eingesetzt. Leider ist mir aber nicht klar was du mit dem

F_{n + 9}

gemacht hast.

Könntest du mir das nochmal erläutern?
Den selben schritt mit dem einsetzen in

F_{n + 10}

habe ich bereits selber versucht nur da hat mich das

F_{n + 9}

gestört! Scheinbar gibt es ja eine Lösung dazu, nur leider verstehe ich diese nicht ganz.

Viele Grüße!

Roman-22

11:57 Uhr, 08.12.2016

Da Werner

d z t

offenbar offline ist:

>

was du mit dem Fn+9 gemacht hast.
Werner hat als Induktionsannahme die Gültigkeit für

n

UND für

n - 1

benutzt und diese somit auch für

F_{(n - 1) + 10} = F_{n + 9}

eingesetzt.
Er hat also benutzt:

F_{n + 10} = F_{n - 2} \cdot F_{10} + F_{n - 1} \cdot F_{11}

UND

F_{n + 9} = F_{n - 3} \cdot F_{10} + F_{n - 2} \cdot F_{11}

und wenn du diese Gleichungen addierst und rechts bei den Summenkoeffizienten von

F_{10}

und

F_{11}

die Fibo-Definition anwendest, kommst du sofort auf

F_{(n + 1) + 10} = F_{(n + 1) - 2} \cdot F_{10} + F_{(n + 1) - 1} \cdot F_{11}

und bist fertig.

Damit ist es aber auch erforderlich, vorher die Induktionsvoraussetzung für

n = 2

UND für

n = 3

zu zeigen.

R

Noritz aktiv_icon

13:22 Uhr, 08.12.2016

Danke! Ich glaube ich habe es jetzt!
Das mit dem n-1 kann ich machen weil ich das für 3 beweisen habe oder?
Schicke das nachher nochmal komplett rein, wäre toll wenn da nochmal wer drüber sehen kann :-)

Roman-22

13:34 Uhr, 08.12.2016

>

Das mit dem

n - 1

kann ich machen weil ich das für 3 beweisen habe oder?
Ja, da deine Rekursion auf zwei Vorgänger zurückgreift, benötigst du für den Induktionsbeweis auch zwei aufeinander folgende Startwerte.

Weil es für

n = 2

und

n = 3,

also für

F_{12}

und

F_{13}

gilt, folgt aus deinem Beweis, dass es auch für

F_{14}

gilt. usw.

Stephan4

14:07 Uhr, 08.12.2016

Noritz, die Behauptung, die Du ganz zu Beginn mit "Ich muss folgende Behauptung ..." geschrieben hast, ist Teil der Induktionsvoraussetzung.

Zur Induktionsvoraussetzung gehört auch, dass es sich um eine Fibonacci-Folge handelt, also

F_{n} = F_{n - 1} + F_{n - 2}

Mit dieser Induktionsvoraussetzung hat Werner-Salomon den Induktionsschluss geführt, indem er die Richtigkeit der Induktionsbehauptung (dass die Induktionsvoraussetzung für

n + 1

gültig ist) darstellt.

Den Induktionsanfang hast Du anfangs ja selbst schon geprüft und damit die ursprüngliche Behauptung für

n = 2

bewiesen.

:-)

Roman-22

14:29 Uhr, 08.12.2016

@Stephan4
Auf welche konkrete Frage hast du jetzt eigentlich geantwortet, nachdem Noritz meinte, er hätte es verstanden?

>

Noritz, die Behauptung, die Du ganz zu Beginn mit "Ich muss folgende Behauptung ..." geschrieben hast, ist Teil der Induktionsvoraussetzung.
Nein, diese Definition der Folge hat mit der Induktionsvoraussetzung nichts zu tun, aber natürlich wird sie im Beweis zu verwenden sein.

>

Mit dieser Induktionsvoraussetzung hat Werner-Salomon den Induktionsschluss geführt
Nein, wie gesagt ist die Folgendefinition nicht Teil der IV. Werner hat als IV vorausgesetzt und in seinem Beweis verwendet, dass die behauptete Aussage für

n

UND

n - 1

(also

F_{n + 10} = . .

. und

F_{n + 9} = ...)

richtig sei und damit den Beweis geführt, dass die Aussage auch für

n + 1

(also

F_{n + 11} = ...)

gültig ist.

>

Den Induktionsanfang hast Du anfangs ja selbst schon geprüft und damit die ursprüngliche Behauptung für

n = 2

bewiesen.
Wie ebenfalls schon oben geschrieben ist das aber als IA zu wenig. Es muss zusätzlich auch noch die Richtigkeit für

n = 3

gezeigt werden, damit der Beweis greift.

Noritz aktiv_icon

21:04 Uhr, 08.12.2016

Ich habe die Aufgabe jetzt so gelöst. Das mit dem 42 ist beabsichtig. Ich hoffe das stört nicht zu sehr. Sonst ändere ich das gerne noch ab! Wäre lieb wenn mir wer sagt, ob noch was falsch ist :-)

Definition:

F_{0} = F_{1} = 1, F_{n} = F_{n - 1} + F_{n - 2}

bei

n \geq 2

IA:

für n = 2;

F_{44} = F_{42} + F_{43}

-> Korrekt laut Def.

für n = 3;

F_{45} = F_{n} * F_{42} + F_{2} * F_{43}

= 1 * F_{42} + 2 * F_{43}

= F_{42} + F_{43} + F_{43}

= F_{44} + F_{43}

-> Korrekt laut Def.

IV:

n = k;

F_{k + 42} = F_{k - 2} * F_{42} + F_{k - 1} * F_{43}

für

n \geq 2

n = k - 1;

F_{k + 41} = F_{k - 3} * F_{42} + F_{k - 2} * F_{43}

für

n \geq 3

IBeh:
n = k + 1;

F_{k + 43} = F_{k - 1} * F_{42} + F_{k} * F_{43}

IBew:

F_{k + 43} = F_{k + 42} + F_{k + 41}

= F_{k - 2} * F_{42} + F_{k - 1} * F_{43} + F_{k - 3} * F_{42} + F_{k - 2} * F_{43}

= F_{42} (F_{k - 2} + F_{k - 3}) + F_{43} (F_{k - 1} + F_{k - 2})

= F_{k - 1} * F_{42} + F_{k} * F_{43}

-> Korrekt

Roman-22

23:32 Uhr, 08.12.2016

Warum deine Indizes alle um

32

zu groß sind ist mir schleierhaft. Das stimmt keinesfalls mit der ursprünglichen Angabe überein. Warum das?
Ansonsten scheints hinzukommen.

Stephan4

00:36 Uhr, 09.12.2016

Dies Formel mit Beweis durch

v . I

. ist auch hier zu finden:

http//2000clicks.com/mathhelp/BasicRecurrenceRelationsFibonacci.aspx

(gleich das erste Beispiel)

:-)

1342220

1341915

	Status: nicht eingeloggt	Noch nicht registriert?