Fibonacci, Induktktion < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:53 So 05.11.2006 | | Autor: | unwanted |
| Aufgabe | Die Fibonacci Zahlen seien definiert durch
[mm] f_{1} [/mm] = [mm] f_{2} [/mm] = 1, [mm] f_{n-1} [/mm] + [mm] f_{n-2}(n\ge3).
[/mm]
Man zeige durch vollständige Induktion, dass für alle [mm] n\ge1 [/mm] gilt
[mm] \summe_{i=1}^{n}f_{2i-1} [/mm] = [mm] f_{2n} [/mm] . |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
man denkt nun versteht man die vollständige induktion und dann kommt eine aufgabe wie diese?
was ist mein induktions anfang und was muss ich zeigen?
es tut mir leid dass ich keinen ansatz für diese aufgabe habe, aber ich habe selber sehr lange probiert etwas zu finden, und nun bin ich doch wieder hier gelandet mit der hoffnung jemand hier kann mir das verständlich machen. danke
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:12 So 05.11.2006 | | Autor: | felixf |
Hallo!
> Die Fibonacci Zahlen seien definiert durch
> [mm]f_{1}[/mm] = [mm]f_{2}[/mm] = 1, [mm]f_{n-1}[/mm] + [mm]f_{n-2}(n\ge3).[/mm]
> Man zeige durch vollständige Induktion, dass für alle
> [mm]n\ge1[/mm] gilt
> [mm]\summe_{i=1}^{n}f_{2i-1}[/mm] = [mm]f_{2n}[/mm] .
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> man denkt nun versteht man die vollständige induktion und
> dann kommt eine aufgabe wie diese?
>
> was ist mein induktions anfang und was muss ich zeigen?
Na, so wie immer: du schaust dir die Gleichung fuer $n = 1$ an. Hier ist die Gleichung [mm] $\sum_{i=1}^n f_{2i-1} [/mm] = [mm] f_{2n}$. [/mm] Wenn du $n = 1$ einsetzt, steht da [mm] $f_1 [/mm] = [mm] f_2$. [/mm] Und das stimmt per Induktion.
So. Und jetzt musst du den Induktionsschritt finden. Das ist auch ganz einfach. Hast du eine Idee? Geht wirklich genauso wie sonst auch immer...
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:37 So 05.11.2006 | | Autor: | unwanted |
Wenn du n = 1 einsetzt, steht da $ [mm] f_1 [/mm] = [mm] f_2 [/mm] $. Und das stimmt per Induktion.
stimmt dies da die zahlen definiert sind durch f1 = f2 ....... ist das richtig dass so zu schreiben?
vielen dank für deine starthilfe. ich bin bis hierher gekommen :
[mm] \summe_{i=1}^{n+1}f_{2i-1} [/mm] = [mm] \summe_{i=1}^{n}f_{2i-1}+f_{2n+1}=f_{2n+2}
[/mm]
ist dies soweit richtig? und nun muss ich doch noch irgendwas zeigen. ich werde mich mal weiter daran versuchen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:59 So 05.11.2006 | | Autor: | ullim |
Hi,
unwanted, ich sehe nicht wo in meiner Antwort ein Fehler sein soll. S. auch den Kommentar von angela. Ich würde dich bitten, deine Kommentierung zurück zu nehmen. Danke.
mfg ullim
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:25 So 05.11.2006 | | Autor: | unwanted |
es tut mir leid aber das hilf mir nicht weiter oder? was is mit nach IV gemeint?
meine aufgabe ist doch
$ [mm] \summe_{i=1}^{n}f_{2i-1}=f_{2n} [/mm] $
durch vollständige induktion zu beweisen
|
|
|
| |
|
> es tut mir leid aber das hilf mir nicht weiter oder? was is
> mit nach IV gemeint?
Hallo,
mit IV ist hier keine römische Zahl gemeint, sondern die I nduktions v oraussetzung, eine recht verbreitete Abkürzung. Oft wird auch "Induktionsannahme" gesagt.
Ich habe den Verdacht, daß Du das Prinzip der vollständigen Induktion noch nicht verstanden hast.
Man wendet es oft an, wenn es gilt, eine Aussage für alle n [mm] \in \IN [/mm] zu beweisen (oder für alle natürlichen Zahlen > einer bestimmten).
Das Kochrezept:
Induktionsanfang: zeige, daß die zu beweisende Aussage für n=1 gilt.
Induktionsvoraussetzung: nimm an, sie würde für alle n gelten.
Induktionsschluß: zeige, daß sie unter dieser Voraussetzung auch für n+1 gilt.
Ist Dir das gelungen, ist die Aussage für alle n bewiesen. Du hast bei n=1 "geankert" und gezeigt, daß sie für die daruffolgende Zahl, 1+1 auch gilt, und weil sie dafür gilt, auch für (1+1)+1 und immer so weiter.
Wenn Du es im Moment nicht 100- % verstehst, zerbrich Dir nicht den Kopf darüber. Wende das Kochrezept an. Steter Tropfen höhlt den Stein, irgendwann knallt's und man hat's verstanden.
Also [mm] f_1=f_2=1, f_n=f_{n-1}+f_{n-2}
[/mm]
In Worten: Du erhältst die nächste Fibonaccizahl, indem Du die beiden vorhergehenden addierst.
Schreib doch jetzt einfach mal für Dich die ersten paar Fibonaccizahlen auf!
> [mm]\summe_{i=1}^{n}f_{2i-1}=f_{2n}[/mm]
>
> durch vollständige induktion zu beweisen
Induktionsanfang (IA): zeige die Gültigkeit für n=1.
Das hattest Du ja bereits getan.
Induktionsvoraussetzung (IV): Es gelte [mm] \summe_{i=1}^{n}f_{2i-1}=f_{2n} [/mm] für alle n [mm] \in \IN.
[/mm]
Induktionsschluß (IS): Zu zeigen: die Behauptung gilt für n+1, d.h. es ist zu zeigen
[mm] \summe_{i=1}^{n+1}f_{2i-1}=f_{2(n+1)}=f_{2n+2}
[/mm]
Bew. Es ist
[mm] \summe_{i=1}^{n+1}f_{2i-1}
[/mm]
[mm] =\summe_{i=1}^{n}f_{2i-1} +f_{2(n+1)-1}
[/mm]
[mm] =\underbrace{\summe_{i=1}^{n}f_{2i-1}}_{IV einsetzen} +f_{2n+1}
[/mm]
= ...
Nun solltest Du die Summe zweier aufeinanderfolgender Fibonaccizahlen dort stehen haben. Erinnere Dich, wie die Fibonaccizahlen gebildet werden, und Du bist am Ziel.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:45 So 05.11.2006 | | Autor: | unwanted |
vielen dank, das war wieder eine gute hilfe. ich habe die theorie verstanden, nur an der umsetzung mangelts es noch. aber um so mehr man übt um so besser wird es.
ich bin nun hier...
Es ist
$ [mm] \summe_{i=1}^{n+1}f_{2i-1} [/mm] $
$ [mm] =\summe_{i=1}^{n}f_{2i-1} +f_{2(n+1)-1} [/mm] $
$ [mm] =\underbrace{\summe_{i=1}^{n}f_{2i-1}}_{IV einsetzen} +f_{2n+1} [/mm] $
nun setze ich ein und bekomme
= [mm] f_{2n}+f_{2n+1}
[/mm]
ist das nun was zu zeigen war? das wenn [mm] A_{n} [/mm] gilt auch [mm] A_{n+1} [/mm] gilt ?
|
|
|
| |
|
> = [mm]f_{2n}+f_{2n+1}[/mm]
>
> ist das nun was zu zeigen war?
Fast!
Irgendwo in Deiner Aufgabenstellung steht (leider etwas rudimentär...): [mm] f_n=f_{n-1}+f_{n-2}.
[/mm]
Wenn man sich von den n's ein bißchen frei macht und dieser Gleichung Sinn einhaucht, heißt das: jede Fibonaccizahl erhalt man durch Addition ihrer beiden Vorgänger.
= [mm]f_{2n}+f_{2n+1}[/mm]
Hier haben wir zwei aufeinanderfolgende Fibonaccizahlen, die addiert werden. Laut "Bastelanleitung für Fibonaccizahlen" ergibt das die nächste.
Na, was kommt nach 2n und 2n+1??? 2n+2=2(n+1)
Also:
= [mm] f_{2(n+1)}
[/mm]
Hast du Dir die ersten Fibonaccizahlen mal ausgerechnet und aufgeschrieben? Ich habe die ersten 10 auf dem Zettel vor mir!
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:31 So 05.11.2006 | | Autor: | unwanted |
ich habe mir die zahlen auch mal aufgeschrieben. und ich sehe dass alles einen sinn ergibt.
nun bin ich mir nur nicht sicher wie ich den induktionsschluss korekt aufschreibe.
ich werde hier mal einen versuch machen.
Induktionsschritt:
wie setzen voraus, dass
$ [mm] \summe_{i=1}^{n}f_{2i-1}=f_{2n} [/mm] $ für alle n [mm] \in \IN [/mm] gilt und zeigen
das die behauptung auch für n+1 gilt, d.h. zu zeigen ist:
[mm] \summe_{i=1}^{n+1}f_{2i-1} [/mm] = [mm] f_{2(n+1)} [/mm] = [mm] f_{2n+2}
[/mm]
Beweis: Es ist
[mm] \summe_{i=1}^{n+1}f_{2i-1} [/mm] = [mm] \summe_{i=1}^{n}f_{2i-1} [/mm] + [mm] f_{2(n+1)-1} [/mm] = [mm] \summe_{i=1}^{n}f_{2i-1} [/mm] + [mm] f_{2n+1} [/mm] = [mm] f_{2n} [/mm] + [mm] f_{2n+1} [/mm] = [mm] f_{2(n+1)}
[/mm]
was zu zeigen war
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:56 So 05.11.2006 | | Autor: | felixf |
Hallo!
> ich habe mir die zahlen auch mal aufgeschrieben. und ich
> sehe dass alles einen sinn ergibt.
>
> nun bin ich mir nur nicht sicher wie ich den
> induktionsschluss korekt aufschreibe.
>
> ich werde hier mal einen versuch machen.
>
> Induktionsschritt:
>
> wie setzen voraus, dass
>
> [mm]\summe_{i=1}^{n}f_{2i-1}=f_{2n}[/mm] für alle n [mm]\in \IN[/mm] gilt
> und zeigen
>
> das die behauptung auch für n+1 gilt, d.h. zu zeigen ist:
>
> [mm]\summe_{i=1}^{n+1}f_{2i-1}[/mm] = [mm]f_{2(n+1)}[/mm] = [mm]f_{2n+2}[/mm]
>
> Beweis: Es ist
>
> [mm]\summe_{i=1}^{n+1}f_{2i-1}[/mm] = [mm]\summe_{i=1}^{n}f_{2i-1}[/mm] +
> [mm]f_{2(n+1)-1}[/mm] = [mm]\summe_{i=1}^{n}f_{2i-1}[/mm] + [mm]f_{2n+1}[/mm] = [mm]f_{2n}[/mm]
> + [mm]f_{2n+1}[/mm] = [mm]f_{2(n+1)}[/mm]
>
> was zu zeigen war
![[ok]](/images/smileys/ok.gif "[ok]")
LG Felix
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 20:08 So 05.11.2006 | | Autor: | unwanted |
:) na dann, wenn das richtig ist, vielen dank an alle, für die geduld und die gute hilfe :)
|
|
|
| |
|
Hi Leute,
irgendwo ist in der behaupteten Formel der Wurm drin:
[mm] $f_1=1, f_2=1,f_3=2, f_4=3, f_5=5, f_6=8, f_7=13 \ldots$.
[/mm]
[mm] $f_1+f_3=4$, [/mm] aber 4 ist kein Glied der Fibonacci-Folge!
[mm] $f_1+f_3+f_5=8=f_6$,
[/mm]
mit dem Bildungsgesetz [mm] $\summe_{i=1}^4 f_{2i-1}=f_{2*4}$.
[/mm]
Scheint also erst für $n [mm] \ge [/mm] 3$ (und *nicht* wie in der Aufgabenstellung $n [mm] \ge [/mm] 1$) zu gelten.
Gruß
zahlenspieler
|
|
|
| |
|
Hallo,
da bin ich wohl zu schnell vorgeprescht; also einfach ignorieren, hatte mich verrechnet. Wenn ich könnte würd ich den Mist den ich da geschrieben habe, löschen.
Is schon peinlich
Mfg
zahlenspieler
|
|
|
| |
|
| Status: |
(Korrektur) Korrekturmitteilung  | | Datum: | 19:15 So 05.11.2006 | | Autor: | angela.h.b. |
> Is schon peinlich
Quatsch!
Wo gehobelt wird, fallen Späne...
Gibt es einen. der noch nie wirr geworden ist? Bestimmt nicht!
Es kommt darauf an, in welchen Verhältnis Verwirrungszustände zu Zuständen der Nichtverwirrtheit stehen, und da stehst du ganz gut da, oder?
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Korrektur) Korrekturmitteilung | | Datum: | 18:49 So 05.11.2006 | | Autor: | angela.h.b. |
> Hi Leute,
> irgendwo ist in der behaupteten Formel der Wurm drin:
> [mm]f_1=1, f_2=1,f_3=2, f_4=3, f_5=5, f_6=8, f_7=13 \ldots[/mm].
>
> [mm]f_1+f_3=4[/mm], aber 4 ist kein Glied der Fibonacci-Folge!
4 ist kein Glied der Fibonaccifolge, aber das macht nichts:
[mm] f_1+f_3=1+2=3=f_4.
[/mm]
>
> [mm]f_1+f_3+f_5=8=f_6[/mm],
> mit dem Bildungsgesetz [mm]\summe_{i=1}^4 f_{2i-1}=f_{2*4}[/mm].
Für n=4 erhalte ich mit der in der Aufgabe zu beweisenden Behauptung
[mm] \summe_{i=1}^4 f_{2i-1}=f_{2*4} [/mm] und das stimmt:
es ist [mm] f_{2*1-1}+f_{2*2-1}+f_{2*3-1}+f_{2*4-1}=f_1+f_3+f_5+f_7=1+2+5+13=21=f_8
[/mm]
Alles in Ordnung!
(Das muß auch so sein: sonst hätte man es ja nicht per Induktion beweisen können...)
>
> Scheint also erst für [mm]n \ge 3[/mm] (und *nicht* wie in der
> Aufgabenstellung [mm]n \ge 1[/mm]) zu gelten.
Es stimmt für alle n [mm] \in \IN.
[/mm]
n=1: [mm] 1=f_1=f_2=1 [/mm]
n=2: [mm] 3=f_1+f_3=f_4=3
[/mm]
n=3 [mm] 8=f_1+f_3+f_5=f_6=8
[/mm]
Gruß v. Angela
|
|
|
| |
|
> Hi,
>
> [mm]\summe_{i=1}^{n}f_{2i-1}=f_{2n}[/mm] nach IV und
>
> [mm]f_{2n}+f_{2n+1}=f_{2n+2}[/mm] nach dem Bildungsgesetzt für die
> Fibonacci Folge.
>
> mfg ullim
Hallo,
ich halte ullims als fehlerhaft gekennzeichnete Antwort sowohl für richtig als auch für konstruktiv.
Gruß v. Angela
|
|
|
|
