Fibonacci-Folge < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 07:43 Do 27.01.2011 | | Autor: | itse |
| Aufgabe | Beweise folgende Aussage mittels vollständiger Induktion:
für n [mm] \ge [/mm] 3: 1 < [mm] \bruch{f_{n+1}}{f_n} [/mm] < 2
[mm] f_1 [/mm] = [mm] f_2 [/mm] = 1, [mm] f_{n+2} [/mm] = [mm] f_{n+1}+f_n [/mm] |
Guten Morgen,
bei [mm] f_n [/mm] handelt es sich um die Fibonacci-Folge.
Als erstes der Induktionsanfang:
n=3:
1 < [mm] \bruch{f_{4}}{f_3} [/mm] < 2
1 < [mm] \bruch{3}{2} [/mm] < 2 (wahr)
n=4:
1 < [mm] \bruch{f_{5}}{f_4} [/mm] < 2
1 < [mm] \bruch{5}{3} [/mm] < 2 (wahr)
Nun die Annahme:
1 < [mm] \bruch{f_{n+1}}{f_n} [/mm] < 2 gültig für n [mm] \ge [/mm] 3
Behauptung n -> n+1
1 < [mm] \bruch{f_{n+2}}{f_{n+1}} [/mm] < 2 für n [mm] \ge [/mm] 3
Beweis:
Ich muss ja ausgehend von der Induktionsbehauptung mit Hilfe der Induktionsannahme auf die Abschätzung < 2 kommen.
1 < [mm] \bruch{f_{n+2}}{f_{n+1}} [/mm] = [mm] \bruch{f_{n+1}+f_n}{f_{n+1}} [/mm] = [mm] \bruch{f_n}{f_{n+1}} [/mm] + 1
1 < 2, somit kann ich die 1 vernachlässigen
Leider steht aber der Bruch [mm] \bruch{f_n}{f_{n+1}} [/mm] genau andersherum da, wie in der Induktionsannahme.
Wie komme ich hier weiter, wie muss ich umformen, um die Induktionsannahme verwenden zu können damit das Ganze kleiner 2 ist?
Vielen Dank
itse
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:08 Do 27.01.2011 | | Autor: | fred97 |
Wir haben:
(1) $ [mm] \bruch{f_{n+2}}{f_{n+1}} [/mm] $ = $ [mm] \bruch{f_{n+1}+f_n}{f_{n+1}} [/mm] $ = $ [mm] \bruch{f_n}{f_{n+1}} [/mm] $ + 1
und
(2) 1 < $ [mm] \bruch{f_{n+1}}{f_n} [/mm] $ < 2
Aus (2) folgt: 1/2 < $ [mm] \bruch{f_{n}}{f_{n+1}} [/mm] $ < 1
Setze das in (1) ein.
FRED
|
|
|
| |
|
Guten Tag itse,
Fred ist mir (wieder einmal) zuvor gekommen ...
Ich habe nur noch zwei kleine (aber zentrale) Anmerkungen
zu machen.
> Beweise folgende Aussage mittels vollständiger Induktion:
>
> für n [mm]\ge[/mm] 3: 1 < [mm]\bruch{f_{n+1}}{f_n}[/mm] < 2
>
> [mm]f_1[/mm] = [mm]f_2[/mm] = 1, [mm]f_{n+2}[/mm] = [mm]f_{n+1}+f_n[/mm]
> Guten Morgen,
>
> bei [mm]f_n[/mm] handelt es sich um die Fibonacci-Folge.
>
> Als erstes der Induktionsanfang:
> n=3:
>
> 1 < [mm]\bruch{f_{4}}{f_3}[/mm] < 2
>
> 1 < [mm]\bruch{3}{2}[/mm] < 2 (wahr)
>
> n=4:
>
> 1 < [mm]\bruch{f_{5}}{f_4}[/mm] < 2
>
> 1 < [mm]\bruch{5}{3}[/mm] < 2 (wahr)
>
> Nun die Annahme:
>
> 1 < [mm]\bruch{f_{n+1}}{f_n}[/mm] < 2 gültig für n [mm]\ge[/mm] 3
Vorsicht ! Dies könnte man so auffassen, dass hier die
zu behauptende Ungleichungskette für alle n mit [mm] n\ge3
[/mm]
vorausgesetzt wird. Dies geht natürlich nicht. Auf analoge Weise
könnte man sonst ebenso etwa die Behauptung "alle n mit [mm] n\ge3 [/mm] sind Primzahlen"
"beweisen".
Es ist wichtig, dass die Induktionsvoraussetzung
[mm] $\blue{1\ <\ \bruch{f_{n+1}}{f_n}< 2}$ [/mm] gültig für [mm] $\blue{n\ge 3}$
[/mm]
sich hier nur auf ein bestimmtes n mit [mm] n\ge3 [/mm] bezieht und
nicht auf alle solchen n !
> Behauptung n -> n+1
>
> 1 < [mm]\bruch{f_{n+2}}{f_{n+1}}[/mm] < 2 für n [mm]\ge[/mm] 3
>
> Beweis:
>
> Ich muss ja ausgehend von der Induktionsbehauptung ![[haee]](/images/smileys/haee.gif "[haee]")
> mit Hilfe der Induktionsannahme auf die Abschätzung < 2
> kommen.
Dies ist ebenfalls zumindest fehlerhaft ausgedrückt.
Um die Induktionsbehauptung zu beweisen, darf man
doch nicht "von dieser ausgehen" (also sie voraussetzen) !
> 1 < [mm]\bruch{f_{n+2}}{f_{n+1}}[/mm] = [mm]\bruch{f_{n+1}+f_n}{f_{n+1}}[/mm]
> = [mm]\bruch{f_n}{f_{n+1}}[/mm] + 1
>
> 1 < 2, somit kann ich die 1 vernachlässigen
>
> Leider steht aber der Bruch [mm]\bruch{f_n}{f_{n+1}}[/mm] genau
> andersherum da, wie in der Induktionsannahme.
>
> Wie komme ich hier weiter, wie muss ich umformen, um die
> Induktionsannahme verwenden zu können damit das Ganze
> kleiner 2 ist?
(siehe Freds Antwort)
LG Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:50 Do 27.01.2011 | | Autor: | fred97 |
> Guten Tag itse,
>
> Fred ist (mir wieder einmal) zuvor gekommen ...
>
Hallo Al,
das tut mir leid ....
Gruß FRED
|
|
|
| |
|
> > Fred ist mir (wieder einmal) zuvor gekommen ...
> Hallo Al,
>
> das tut mir leid ....
>
> Gruß FRED
Guten Morgen Fred,
für deine Zuvorkommenheit brauchst du dich keineswegs
zu entschuldigen !
 Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:38 Do 27.01.2011 | | Autor: | fred97 |
> > > Fred ist mir (wieder einmal) zuvor gekommen ...
>
>
> > Hallo Al,
> >
> > das tut mir leid ....
> >
> > Gruß FRED
>
>
> Guten Morgen Fred,
>
> für deine Zuvorkommenheit brauchst du dich keineswegs
> zu entschuldigen !
>
>
> Al
>
...... schönes Wortspiel ....
FRED
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:38 Do 27.01.2011 | | Autor: | itse |
Hallo,
danke für die Antworten, der Beweis sieht nun wie folgt aus:
2. Induktionsschluss
a) Induktionsannahme: [mm] \exists n\in\IN\sub [/mm] mit n [mm] \ge [/mm] 3 für das gilt: 1 < [mm] \bruch{f_{n+1}}{f_n} [/mm] < 2
b) Induktionsbehauptung n -> n+1 : 1 < [mm] \bruch{f_{n+2}}{f_{n+1}} [/mm] < 2
c) Induktionsbeweis
1 < [mm] \bruch{f_{n+2}}{f_{n+1}} [/mm] = [mm] \bruch{f_{n+1}+f_n}{f_{n+1}} [/mm] = [mm] \bruch{f_n}{f_{n+1}} [/mm] + 1 *
Nun ist die Annahme (Voraussetzung): 1 < [mm] \bruch{f_{n+1}}{f_n} [/mm] < 2 => [mm] \bruch{1}{2} [/mm] < [mm] \bruch{f_n}{f_{n+1}} [/mm] < 1
Somit kann [mm] \bruch{f_n}{f_{n+1}} [/mm] dadurch abgeschätzt werden also [mm] \bruch{f_n}{f_{n+1}} [/mm] < 1
* < 1 +1 < 2
So müsste es nun doch stimmen?
Müsste man nicht noch die andere Richtung zeigen?
Also in etwa so:
[mm] \bruch{f_{n+2}}{f_{n+1}} [/mm] < 2
[mm] \bruch{f_{n+1}+f_n}{f_{n+1}} [/mm] < 2
1 + [mm] \bruch{f_n}{f_{n+1}} [/mm] < 2
[mm] \bruch{f_n}{f_{n+1}} [/mm] < 1
=> 1 < [mm] \bruch{f_{n+1}}{f_n}
[/mm]
Beste Grüße
itse
|
|
|
| |
|
Hallo itse,
es geht wohl eigentlich nur noch um geeignete Formulierungen,
um die Idee des Beweises klar rüberzubringen. Ich will deshalb
nicht mehr an deiner Lösung "herumflicken", sondern gebe
einfach eine eigene Version an, in der ich absichtlich nicht an
sprachlichen Formulierungen spare.
2.) Induktionsschritt
a) Induktionsannahme:
n sei eine natürliche Zahl mit [mm] n\ge [/mm] 3 , für welche die
Ungleichungskette 1 < [mm]\bruch{f_{n+1}}{f_n}[/mm] < 2 zutrifft
b) Induktionsbehauptung:
Unter der Voraussetzung (a) gilt dann auch 1 < [mm]\bruch{f_{n+2}}{f_{n+1}}[/mm] < 2
c) Beweis:
Es ist [mm]\bruch{f_{n+2}}{f_{n+1}}\ =\ \bruch{f_n+f_{n+1}}{f_{n+1}}\ =\ \underbrace{\bruch{f_n}{f_{n+1}}}_{T}+1[/mm] (***)
Aus der Induktionsvoraussetzung 1 < [mm]\bruch{f_{n+1}}{f_n}[/mm] < 2
folgt durch Kehrwertbildung:
$\ 1\ >\ [mm] \bruch{f_n}{f_{n+1}} [/mm] > [mm] \frac{1}{2}$
[/mm]
bzw. [mm] $\frac{1}{2}\ [/mm] <\ [mm] \underbrace{\bruch{f_n}{f_{n+1}}}_{T}\ [/mm] <\ 1 $
Durch Addition von 1 folgt:
[mm] $\frac{3}{2}\ [/mm] <\ [mm] \bruch{f_n}{f_{n+1}}+1\ [/mm] <\ 2 $
und, weil $\ 1\ <\ [mm] \frac{3}{2}$ [/mm] und wegen (***) :
$\ 1\ <\ [mm] \bruch{f_{n+2}}{f_{n+1}}\ [/mm] <\ 2$
3.) Induktionsschluss
Da die Ungleichungskette für n=3 zutrifft (Verankerung) und
der Induktionsschritt für alle n mit [mm] n\ge3 [/mm] bewiesen ist, folgt
nach dem Prinzip der vollständigen Induktion, dass sie
für alle [mm] n\in\IN [/mm] mit [mm] n\ge3 [/mm] gültig ist, also:
[mm] (\forall n\in\IN [/mm] , [mm] n\ge3) [/mm] 1 < [mm]\bruch{f_{n+1}}{f_n}[/mm] < 2 Q.E.D.
(dies ist jetzt natürlich ausführlicher geraten als man einen
derartigen Beweis gewöhnlich notiert ...)
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:56 Do 27.01.2011 | | Autor: | itse |
Hallo Al,
Vielen Dank
Gruß
itse
|
|
|
|
