Fibonacci Zahlen + Vollst. Ind < Sonstiges < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:52 So 30.09.2007 | | Autor: | Paul1985 |
| Aufgabe | Die Fibonacci Zahlen sind [mm] a_{0} [/mm] = 1, [mm] a_{1} [/mm] = 1 und [mm] a_{n}+1 [/mm] = [mm] a_{n} [/mm] + [mm] a_{-1} [/mm] für n [mm] \ge [/mm] 1.
Wir erhalten damit folgende Zahlenfolge 1; 1; 2; 3; 5; 8; 13; 21; 34;...
Zeige mit vollständiger Induktion, dass 1 [mm] \le\bruch{a_{n+1}}{a_{n}} \le [/mm] 2 gilt für n [mm] \ge [/mm] 0.
Es ist klar das alle Fibonacci Zahlen positiv sind.
|
Lösung:
n = 0 : 1 [mm] \le \bruch{a_{1}}{a_{0}} \le [/mm] 2 [mm] \gdw [/mm] 1 [mm] \le [/mm] 1 [mm] \le [/mm] 2
n = 1 ; 1 [mm] \le \bruch{a_{2}}{a_{1}} \le [/mm] 1 [mm] \gdw [/mm] 2 [mm] \le [/mm] 2 [mm] \le [/mm] 2
Induktionsvoraussetzung: Für alle Zahlen m [mm] \le [/mm] n -1 gilt 1 [mm] \le \bruch{a_{m+1}}{a_{m}} \le [/mm] 2
Induktionsschluss: 1 [mm] \le \bruch{a_{n+1}}{a_{n}} [/mm] = [mm] \bruch{a_{n}+a_{n-1}}{a_{n}} [/mm] = [mm] \underbrace{\bruch{a_{n}}{a_{n}}}_{=1} [/mm] + [mm] \bruch{a_{n-1}}{a_{n}} [/mm] = 1 + [mm] \underbrace{\bruch{a_{n-1}}{a_{n-1}+a_{n-2}}}_{ \ge 2} \le [/mm] 2
Diese Aufgabe + Lösung habe ich vor mir liegen..
Kann mir es bitte jemand "für dumme " erklären ? Ich verstehe irgendwie kaum was davon :(
Fibonacci Zahlen sind mir bekannt.
Vielen Dank,
P
|
|
| |
|
Hallo Paul,
da scheint mir aber was nicht zu stimmen:
Der Bruch im vorletzten Schritt, also [mm] $\bruch{a_{n-1}}{a_{n-1}+a_{n-2}}$ [/mm] ist doch sicherlich [mm] $\red{\le 1}$. [/mm] Der Nenner ist ja größer als der Zähler.
Dann passt das auch mit der Abschätzung.
Mal ein paar Worte dazu:
Ich nehme an, der Induktionsanfang für $n=0,1$ ist klar?!
Der Induktionsschritt ist wie gewöhnlich von [mm] $n\to [/mm] n+1$
Es wurde hier die sog. "erweiterte Induktionsvoraussetzung" benutzt, in der man annimmt, dass die Aussage, also die Abschätzung für alle Zahlen [mm] $\le [/mm] n$ gilt.
Also nimmt man hier an, die Aussage gilt für alle [mm] $m\le [/mm] n-1$, also [mm] $m+1\le [/mm] n$
gelte, dh. man nimmt an, dass [mm] $1\le\frac{a_{m+1}}{a_m}\le [/mm] 2$ für $m=1,2,...,n-1$ - wie du es auch aufgeschrieben hast.
Obwohl man die eigentlich gar nicht so recht benutzen muss... ![[kopfkratz3]](/images/smileys/kopfkratz3.gif "[kopfkratz3]")
Zum eigentlichen Induktionsbeweis.
Man will zeigen, dass unter der obigen Induktionsvoraussetzung dann auch gefälligst [mm] $1\le\frac{a_{n+1}}{a_n}\le [/mm] 2$ ist
Dazu schreibt man mal die linke Seite hin und benutzt so alles, was man gegeben hat, um das zur rechten Seite umzuformen:
Im Einzelnen:
[mm] $1\le\frac{a_{n+1}}{a_n}$ [/mm] klar, weil [mm] $a_{n+1}\ge a_n$ [/mm] ist, ist der Bruch [mm] $\ge [/mm] 1$
[mm] $=\frac{a_n+a_{n-1}}{a_n}$ [/mm] klar, oder? Einfach im Zähler die Definition der Fibonacci-Folge benutzt: [mm] $a_{n+1}=a_n+a_{n-1}$
[/mm]
[mm] $=1+\frac{a_{n-1}}{a_n}$ [/mm] Bruchrechnen und klar, oder?
[mm] $=1+\frac{a_{n-1}}{a_{n-1}+a_{n-2}}$ [/mm] wieder die Definition der Fibonacci-Folge - dieses Mal im Nenner: [mm] $a_n=a_{n-1}+a_{n-2}$
[/mm]
Hier kann man nun benutzen, dass die Glieder der Fibonacci-Folge sämtlich >0 sind, also [mm] $a_{n-1}+a_{n-2}>a_{n-1}$ [/mm] und damit [mm] $\frac{a_{n-1}}{a_{n-1}+a_{n-2}}\le [/mm] 1$ (Nenner ist größer(-gleich) dem Zähler), also
[mm] $\le [/mm] 1+1=2$
Insgesamt hat man also ohne die ganzen Zwischenschritte
[mm] $1\le\frac{a_{n+1}}{a_n}\le [/mm] 2$
Ist es nun etwas klarer geworden? 
LG
schachuzipus
|
|
|
|
