Fibonacci Induktion

25.10.2012, 21:44

xetory

Auf diesen Beitrag antworten »

Fibonacci Induktion

Hi,
bin seit Stunden mit folgender Aufgabe beschäftigt:

Die Fibonacci-Zahlen $\begin{eqnarray*} a_{n} \end{eqnarray*}$ sind definiert durch:

$\begin{eqnarray*} a_{0}=1; \ a_{1}=1; \ a_{n+1}=a_{n-1}+a_{n} \\\\ n \geq 1 \end{eqnarray*}$

Zeigen Sie mit vollständiger Induktion: Für alle n $\begin{eqnarray*} \in \mathbb N \end{eqnarray*}$ gilt
$\begin{eqnarray*} n\leq a_{n} \leq 2^{n} \end{eqnarray*}$

Mein Ansatz: Zuerst $\begin{eqnarray*} n\leq a_{n} \end{eqnarray*}$ beweisen

Da a0 und a1 schon definiert sind gehe ich direkt zum Induktionsschritt über.

Dazu forme ich $\begin{eqnarray*} a_{n+1}=a_{n-1}+a_{n} \end{eqnarray*}$ für n größer 1

zu $\begin{eqnarray*} a_{n}=a_{n-1}+a_{n-2} \end{eqnarray*}$ für n größer 2

Ich weiß ehrlich gesagt nicht so genau ob dies überhaupt notwendig ist.
Es macht es für mich aber anschaulicher

Nun der eigentliche Schritt: n = n+1

$\begin{eqnarray*} n+1 \leq a_{(n+1)-1}+a_{(n+1)-2} \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow n+1 \leq a_{n}+a_{n-1} \end{eqnarray*}$

und nun? Ehrlich gesagt bin ich ziemlich verwirrt.
Wäre um etwas Hilfe sehr dankbar

25.10.2012, 22:10

Helferlein

Auf diesen Beitrag antworten »

Was weisst Du denn über $\begin{eqnarray*} a_n \end{eqnarray*}$ und $\begin{eqnarray*} a_{n-1} \end{eqnarray*}$ ?

26.10.2012, 15:44

xetory

Auf diesen Beitrag antworten »

ich weiss das $\begin{eqnarray*} a_{n+1}=a_{n-1}+a_{n} \end{eqnarray*}$
Also habe ich nach der vollständigen Induktion wiederrum die Aussage erhalten die ursprünglich bewiesen werden sollte : /

Verwirrt mich da ich meistens nach der Induktion eine wahre logische Aussage erhalte. (z.B. eine Äquivalenz oder z.B 2*2n > 2n).

26.10.2012, 17:17

Helferlein

Auf diesen Beitrag antworten »

Kann Dir grad nicht ganz folgen, vermutlich weil Du deine Induktionsannahme (bzw. -voraussetzung) nicht aufgeschrieben hast.

26.10.2012, 18:41

xetory

Auf diesen Beitrag antworten »

Die Induktionsvoraussetzung ist $\begin{eqnarray*} n\leq a_{n} \end{eqnarray*}$

Gegeben ist
$\begin{eqnarray*} a_{0}=1; \ a_{1}=1; \ a_{n+1}=a_{n-1}+a_{n} \end{eqnarray*}$

Wie gesagt habe ich an+1 zu an umgeformt:

$\begin{eqnarray*} a_{n}=a_{n-1}+a_{n-2} \end{eqnarray*}$

hier n=n+1 für jedes n in Induktionsvoraussetzung:

$\begin{eqnarray*} n+1 \leq a_{(n+1)-1}+a_{(n+1)-2} \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow n+1 \leq a_{n}+a_{n-1} \end{eqnarray*}$

und weiter komme ich leider nicht :/

hoffe ist nun verständlicher

26.10.2012, 19:27

lgrizu

Auf diesen Beitrag antworten »

Betrachte einmal:

$\begin{eqnarray*} a_{n+1}=a_n+a_{n-1} \geq_{\textbf{nach Voraussetzung}} ...... \end{eqnarray*}$

Was muss da jetzt kommen?

Anzeige

26.10.2012, 21:20

xetory

Auf diesen Beitrag antworten »

RE: Fibonacci Induktion
Also ich stehe glaube ich komplett auf dem Schlauch.
Habe ich bisher irgendwas falsch gemacht?

Ich weiss nicht was mir das sagen soll verwirrt

verwirrt

26.10.2012, 21:59

Helferlein

Auf diesen Beitrag antworten »

Dann noch einmal etwas deutlicher: Was gilt nach Induktionsvoraussetzung für $\begin{eqnarray*} a_n \end{eqnarray*}$ und $\begin{eqnarray*} a_{n-1} \end{eqnarray*}$ ?

27.10.2012, 13:57

xetory

Auf diesen Beitrag antworten »

Ich habe mir nun folgendes überlegt:

Nachdem Induktionsschritt n=n+1 habe ich ja folgendes:

$\begin{eqnarray*} \Rightarrow n+1 \leq a_{n}+a_{n-1} \end{eqnarray*}$

Nun addiere ich zu beiden Seiten der Ungleichung (-1)

$\begin{eqnarray*} \Rightarrow n \leq a_{n}+a_{n-1} -1 \end{eqnarray*}$

da der Ausdruck:

$\begin{eqnarray*} a_{n-1} -1 \end{eqnarray*}$

$\begin{eqnarray*} \geq 0 \end{eqnarray*}$ ist (wegen den natürlichen Zahlen )

erhalte ich die Induktionsvoraussetzung:

$\begin{eqnarray*} n\leq a_{n} \end{eqnarray*}$

also ist die Voraussetzung für alle n wahr.

hoffe meine Gedankengang ist soweit verständlich.

27.10.2012, 14:08

lgrizu

Auf diesen Beitrag antworten »

Nein, das ist er nicht, jedenfalls nicht mir.

Du scheinst große Lücken im Induktionsprinzip zu haben und die Beweisform scheint sich dir noch nicht erschlossen zu haben.

Das Prinzip ist Zählen, es gilt für 1 und für alle n+1, also für 1+1=2 und für 2+1=3 usw., also für alle n.

Nun wendet man die Vorraussetzung an, also die Annahme, es sei bereits für ein festes aber beliebiges n gezeigt.

Wir haben also:

Induktionsvoraussetzung:

$\begin{eqnarray*} a_n \geq n \end{eqnarray*}$

Induktionsanfang (hier ist ein doppelter Induktionsanfang notwendig, da wir die Vorraussetzung für zwei aufeinander folgende Zahlen verwenden möchten):

$\begin{eqnarray*} a_0=1 \geq 0 \end{eqnarray*}$ und $\begin{eqnarray*} a_1=1 \geq 1 \end{eqnarray*}$

Soweit in Ordnung. Nun nehmen wir an, die Behauptung gelte für ein festes aber beliebiges n und n-1.

Dann haben wir:

$\begin{eqnarray*} a_{n+1}=a_n+a_{n-1} \end{eqnarray*}$ (hier ist nun auch deutlich, warum man den doppelten Induktionsanfang benötigt)

Jetzt bedeutet das doch nichts anderes, als dass $\begin{eqnarray*} a_n \geq n \end{eqnarray*}$ und $\begin{eqnarray*} a_{n-1} \geq n-1 \end{eqnarray*}$ nach unserer Voraussetzung.

Das ganze nun noch einsetzen und abschätzen.....

27.10.2012, 16:05

xetory

Auf diesen Beitrag antworten »

Das Prinzip der Induktion ist mir schon klar.
Konnte es auch schon mehrmals erfolgreich z.B bei dem
Beweis der geometrischen Summenformel anwenden.
Allerdings bin ich wohl bei solchen Ungleichungen nicht sehr fit.

Die Induktionsvoraussetzung soll ja für alle n gelten (also n+1)

Aus $\begin{eqnarray*} a_n \geq n \end{eqnarray*}$ wird also $\begin{eqnarray*} a_{n+1} \geq n+1 \end{eqnarray*}$

Da an+1 gegeben ist:

$\begin{eqnarray*} a_{n+1}=a_n+a_{n-1} \end{eqnarray*}$

folgt

$\begin{eqnarray*} a_n+a_{n-1}\geq n+1 \end{eqnarray*}$

soweit so gut.

Warum aber aus der Vorraussetzungen jetzt $\begin{eqnarray*} a_{n-1} \geq n-1 \end{eqnarray*}$ folgt ist mir nicht so ganz klar.

Wie ich das nun richtig Abschätze weiss ich auch nicht so genau unglücklich

unglücklich

Oje ich glaube ich Verzweifel noch an der Aufgabe

27.10.2012, 16:21

Helferlein

Auf diesen Beitrag antworten »

Zitat:

Original von xetory
Das Prinzip der Induktion ist mir schon klar.

Anscheinend aber nicht in der hier nötigen Form. Ich nehme an, dir ist nur die Variante bekannt, in der auf den unmittelbaren Vorgänger zurückgegriffen wird, also die Gültigkeit für n+1 aus der für n gefolgert wird.
Hier brauchen wir aber die Variante, die die Gültigkeit für mehrere Vorgänger (hier zwei) voraussetzt, um dann auf n+1 zu schließen.

Man kann das soweit ausdehnen, dass auf alle Vorgänger zurückgegriffen wird. Haben wir eine Aussage für 1,2,...n bewiesen, dann können wir sie auch für n+1 zeigen.
Hier reicht aber wie gesagt die Gültigkeit für n und n-1, um auf n+1 zu schließen.

27.10.2012, 16:27

lgrizu

Auf diesen Beitrag antworten »

Zitat:

Original von xetory
folgt

$\begin{eqnarray*} a_n+a_{n-1}\geq n+1 \end{eqnarray*}$

soweit so gut.

Das folgt nicht, das ist zu zeigen durch Anwendung der Induktionsannahme!!!!!!!

Man kann damit Aussagen beweisen, die sich im abzählbaren Bereich befinden, es gibt auch die sogenannte transfinite Induktion, damit kann man die vollständige Induktion auf beliebige geordnete Klassen übertragen, also den abzählbaren Bereich verlassen, aber das geht jetzt etwas zu weit....

Wie funktioniert denn Induktion? Wir zeigen, dass es für ein bestimmtes n gilt (Induktionsanfang), dann nehmen wir an, wir haben das für ein festes aber beliebiges n gezeigt und zeigen, dass es auch für dessen Nachfolger gilt.

Also einmal ganz ausführlich:

Induktionsannahme:

$\begin{eqnarray*} a_n \geq n \end{eqnarray*}$

Induktionsanfang:

$\begin{eqnarray*} a_0=1 \geq 0 \end{eqnarray*}$ und $\begin{eqnarray*} a_1=1 \geq 1 \end{eqnarray*}$

Induktionsschluss:

Die Induktionsannahme sei für ein festes aber beliebiges n und seinen Vorgänger n-1 bewiesen. Wir betrachten den Nachfolger n+1, also

$\begin{eqnarray*} a_{n+1}\underbrace{=}_{\textbf{nach Definition}}a_{n}+a_{n-1} \end{eqnarray*}$

Nach unserer Annahme ist $\begin{eqnarray*} a_n \geq n \end{eqnarray*}$ und $\begin{eqnarray*} a_{n-1} \geq n-1 \end{eqnarray*}$ (Hier kommt die Induktionsvoraussetzung ins spiel)

Einfaches einsetzen von n+1 auf beiden Seiten ist kein geeigneter Beweis.

Edit:
@Helferlein: Dein part..... Wink

Wink

27.10.2012, 20:36

xetory

Auf diesen Beitrag antworten »

Also ich denke ich habe es soweit verstanden smile

smile

Mir war nicht ganz klar woher das $\begin{eqnarray*} a_{n-1} \geq n-1 \end{eqnarray*}$ kam.
Aber so ergibt das alles Sinn.

Nun zu den Nachfolgern:

Die Annahme ist natürlich immer noch

$\begin{eqnarray*} a_n \geq n \end{eqnarray*}$

es ist zu zeigen, dass:

$\begin{eqnarray*} a_{n+1}\geq n+1 \end{eqnarray*}$

$\begin{eqnarray*} a_{n+1}\underbrace{=}_{\textbf{nach Definition}}a_{n}+a_{n-1} \end{eqnarray*}$

daraus folgt $\begin{eqnarray*} a_n+a_{n-1}\geq n+1 \end{eqnarray*}$

daraus folgt (I) $\begin{eqnarray*} a_{n-1}\geq n+1-a_n \end{eqnarray*}$

laut Voraussetzung: (II) $\begin{eqnarray*} a_{n-1} \geq n-1 \end{eqnarray*}$

(II) in (I) $\begin{eqnarray*} n-1\geq n+1-a_n \end{eqnarray*}$

daraus folgt $\begin{eqnarray*} a_{n}\geq 2 \end{eqnarray*}$

laut Voraussetzung: $\begin{eqnarray*} a_n \geq n \end{eqnarray*}$

Also folgt $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$

Das wäre natürlich eine wahre Aussage für alle natürlichen Zahlen außer {0,1}

So ich hoffe mir reißt man jetzt nicht den Kopf ab LOL Hammer

LOL Hammer

27.10.2012, 23:43

lgrizu

Auf diesen Beitrag antworten »

Warum brichst du dir denn dermaßen einen ab, das ist doch kein schöner Induktionsbeweis......

Du hast noch immer nicht gezeigt, dass unter der Voraussetzung $\begin{eqnarray*} a_n \geq n \end{eqnarray*}$ folgt, dass $\begin{eqnarray*} a_{n+1} \geq n+1 \end{eqnarray*}$ ist....

Du nimmst einfach an, das ganze sei eine wahre Aussage und formulierst dann um, noch einmal: So funktioniert Induktion nicht!!!!

Ich mache dir den Schluss einmal vor, im Prinzip ist das ganze nen Einzeiler:

$\begin{eqnarray*} a_{n+1}\underbrace{=}_{\textbf{nach Definition}} a_n+a_{n-1} \underbrace{\geq}_{\textbf{nach Voraussetzung}} n+n-1 \underbrace{\geq}_{\textbf{für alle }n \geq 2} n+1 \end{eqnarray*}$

28.10.2012, 10:17

xetory

Auf diesen Beitrag antworten »

Verstehe... smile

smile

hätte es auch am liebsten als EInzeiler geschrieben.
Aber habe noch paar Probleme bei den Ungleichungen.
Als ich heute über meine Unterlagen geflogen bin ich
auf folgendes Axiom für geordnete Körper gestoßen:

Aus a > b und c > d folgt a+c > b+d
Total logisch aber ich bin einfach nicht drauf gekommen.
Deswegen dieses umständliche Umformen.

Nun gut, es ist in der Aufgabe zusätzlich zu zeigen, dass:

$\begin{eqnarray*} a_{n} \leq 2^{n} \end{eqnarray*}$

Ich probiers mal kurz und bündig:

IA:

$\begin{eqnarray*} a_0=1 \leq 1 \end{eqnarray*}$
$\begin{eqnarray*} a_1=1 \leq 2 \end{eqnarray*}$

Sei Annahme für a0 und a1 bewiesen:

Folgerung aus Annahme:

$\begin{eqnarray*} a_{n-1}\leq 2^{n-1} \end{eqnarray*}$

IS:

$\begin{eqnarray*} a_{n+1}\underbrace{=}_{\textbf{nach Definition}} a_n+a_{n-1} \underbrace{\leq }_{\textbf{nach Voraussetzung}} 2^{n-1}+2^{n} \end{eqnarray*}$

$\begin{eqnarray*} 2^{n-1}+2^{n}\leq 2^{n+1} <br /> \Rightarrow 2^{n}*\frac{1}{2}\leq 2^{n} \end{eqnarray*}$ (wahr für alle nat. Zahlen)

Die Ungleichung $\begin{eqnarray*} n\leq a_{n} \leq 2^{n} \end{eqnarray*}$ gilt also für alle n größer/gleich 2 (aus vorheriger Induktion)

28.10.2012, 10:29

lgrizu

Auf diesen Beitrag antworten »

Zitat:

Original von xetory
IS:

$\begin{eqnarray*} a_{n+1}\underbrace{=}_{\textbf{nach Definition}} a_n+a_{n-1} \underbrace{\leq }_{\textbf{nach Voraussetzung}} 2^{n-1}+2^{n} \end{eqnarray*}$

Bis hierhin in Ordnung....

Zitat:

Original von xetory
$\begin{eqnarray*} 2^{n-1}+2^{n}\leq 2^{n+1} <br /> \Rightarrow 2^{n}*\frac{1}{2}\leq 2^{n} \end{eqnarray*}$ (wahr für alle nat. Zahlen)

Wie kommst du darauf, dass $\begin{eqnarray*} 2^n+2^{n-1}=2^n \cdot \frac{1}{2} \end{eqnarray*}$ ist ????

Das ist Käse....

Zitat:

Original von xetory
Die Ungleichung $\begin{eqnarray*} n\leq a_{n} \leq 2^{n} \end{eqnarray*}$ gilt also für alle n größer/gleich 2 (aus vorheriger Induktion)

Das ist auch Quatsch, sie gilt für alle n, n=0 und n=1 wurden bereits im Induktionsanfang geprüft....

Wende auf $\begin{eqnarray*} 2^n +2^{n-1} \end{eqnarray*}$ das Distributivgesetz auf den gemeinsamen Faktor $\begin{eqnarray*} 2^{n-1} \end{eqnarray*}$ an.

28.10.2012, 10:50

xetory

Auf diesen Beitrag antworten »

Bin ich jetzt total Banane ? unglücklich

unglücklich

$\begin{eqnarray*} 2^{n-1}+2^{n}\leq 2^{n+1} \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow \frac{2^{n} }{2} +2^{n}\leq 2*2^{n} \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow \frac{2^{n} }{2} \leq 2^{n} \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow \frac{1}{2}*2^{n} \leq 2^{n} \end{eqnarray*}$

28.10.2012, 11:13

lgrizu

Auf diesen Beitrag antworten »

Hammer

jap, stimmt....

Ich frage mich dennoch, warum du dir so dermaßen einen abbrichst....

$\begin{eqnarray*} a_{n+1} \underbrace{=}_{\textbf{nach Definition}}a_n+a_{n-1} \underbrace{\leq}_{\textbf{nach Voraussetzung}} 2^n+2^{n-1} \underbrace{=}_{\textbf{Distributivgesetz}}(2+1) \cdot 2^{n-1}=3 \cdot 2^{n-1} \leq 4 \cdot 2^{n-1}=2^{n+1} \end{eqnarray*}$

28.10.2012, 13:05

xetory

Auf diesen Beitrag antworten »

Ich denke das Umständliche werd ich mit ein bisschen mehr Erfahrung schon ausmerzen smile

smile

Jedenfalls bin ich froh, dass ich diesen Aufgabentyp einigermaßen verstanden habe.
Durch eure Hilfe ist es mir gelungen einige andere vollständige Induktionen bei Ungleichungen richtig zu Lösen.

Ein Lob für die Geduld und natürlich die Mühe

Freude

Freude

Freude

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »