Beweis ohne Induktion < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:15 Mo 13.11.2006 | | Autor: | Brinki |
| Aufgabe | | Ein Frosch steht auf dem ersten Feld eines Spieles mit n nummerierten Feldern. Er darf bei jedem Spielzug entweder ein oder zwei Felder nach vorne hüpfen. Auf wie viele verschiedene Arten kann er zum n-ten Feld gelangen? |
Hallo Forum,
durch Probieren findet man schnell eine Vermutung:
Dass die Kombinationsmöglichkeiten bei n Feldern gleich den n-ten Fibonacci-Zahlen $ [mm] f_n [/mm] $ sind, lässt sich relativ leicht per Induktion zeigen.
Hat jemand eine Idee, wie es auch ohne Induktion geht?
Vielen Dank.
Grüße
Brinki
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:53 Di 21.11.2006 | | Autor: | moudi |
Hallo Brinki
Schwierig, weil die Fibonacci-Zahlen auch rekursiv definiert sind. Man kann aber die explizite Induktion vermeiden, wenn man feststellt, dass die Lösungszahlen die gleiche Rekursion wie die Fibonaccizahlen erfüllen, und dass sie die gleichen Startwerte haben. Dann ist klar, dass es die gleichen Zahlenfolgen sind.
Die Induktion braucht man dann nur für den "allgemeinen" Beweis, dass Zahlenfolgen, die die gleichen Startwerte haben und die gleiche Rekursionsgleichung erfüllen gleich sind, d.h. dass durch eine Rekursion eine eindeutige Zahlenfolge definiert wird.
mfG Moudi
|
|
|
|
