www.vorkurse.de
Ein Projekt von vorhilfe.de
Die Online-Kurse der Vorhilfe

E-Learning leicht gemacht.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Teams · Forum · Wissen · Kurse · Impressum
Forenbaum
^ Forenbaum
Status Mathe-Vorkurse
  Status Organisatorisches
  Status Schule
    Status Wiederholung Algebra
    Status Einführung Analysis
    Status Einführung Analytisc
    Status VK 21: Mathematik 6.
    Status VK 37: Kurvendiskussionen
    Status VK Abivorbereitungen
  Status Universität
    Status Lerngruppe LinAlg
    Status VK 13 Analysis I FH
    Status Algebra 2006
    Status VK 22: Algebra 2007
    Status GruMiHH 06
    Status VK 58: Algebra 1
    Status VK 59: Lineare Algebra
    Status VK 60: Analysis
    Status Wahrscheinlichkeitst

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Uni-Analysis-Induktion" - Fib. Zahl induktiv beweisen
Fib. Zahl induktiv beweisen < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis-Induktion"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Fib. Zahl induktiv beweisen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 15:45 So 08.12.2013
Autor: pc_doctor

Aufgabe
Sei [mm] f_i [/mm] die i-te Fibonacci-Zahl , also [mm] f_0 [/mm] = 0 , [mm] f_1 [/mm] = 1 und [mm] f_n= f_{n-2} [/mm] + [mm] f_{n-1} [/mm] für n > 1
Beweisen Sie für beliebige n,k [mm] \ge [/mm] 0:

[mm] f_k f_n [/mm] + [mm] f_{k+1} f_{n+1} [/mm] = [mm] f_{n+k+1} [/mm]

Hallo , um erst mal diese rekursive Formel [mm] f_k f_n [/mm] + [mm] f_{k+1} f_{n+1} [/mm] = [mm] f_{n+k+1} [/mm] zu verstehen:

Sei n = 2 und k = 1.

=>
[mm] f_1 f_2 [/mm] + [mm] f_2 f_3 [/mm] = [mm] f_4 [/mm]

[mm] f_1 [/mm] ist 1 , [mm] f_2 [/mm] ist = [mm] f_0 [/mm] + [mm] f_1 [/mm] , also 1
Also ist [mm] f_1 f_2 [/mm] 1 ( wird nicht addiert ,oder ? )

Dann ist

[mm] f_2 f_3 [/mm] , also [mm] f_2 [/mm] ist [mm] f_0 [/mm] + [mm] f_1 [/mm] , also 1
[mm] f_3 [/mm] ist [mm] f_1 [/mm] + [mm] f_2 (f_2 [/mm] ist 1 , [mm] f_1 [/mm] ist 1 , also ) :
[mm] f_3 [/mm] ist 2
Also habe ich für [mm] f_2 f_3 [/mm] 1 und 2, welche davon nehme ich jetzt ?

[mm] f_4 [/mm] ist [mm] f_2 [/mm] + [mm] f_3 [/mm] , also 3

Würde erstmal diese komische Formel klären wollen..

Vielen Dank im Voraus.

        
Bezug
Fib. Zahl induktiv beweisen: Weiter gerechnet
Status: (Frage) beantwortet Status 
Datum: 16:26 So 08.12.2013
Autor: pc_doctor

Hallo nochmal,

unabhängig von meiner letzten Frage würde ich gerne trotzdem mit der Induktion weitermachen.

Induktionsanfang: sei n = 0
Dann ist
[mm] f_0 f_0 [/mm] + [mm] f_1 f_1 [/mm] = [mm] f_1 [/mm]
1 = 1 .

Induktionsschritt:
Nehmen an , Aussage [mm] f_k f_n [/mm] + [mm] f_{k+1} f_{n+1} [/mm] = [mm] f_{n+k+1} [/mm] ist richtig für n,k  [mm] \in \IN [/mm]

Zu zeigen ist ; Aussage gilt auch für k+1 , n+1

[mm] f_{k+1} f_{n+1} +f_{k2} [/mm] + [mm] f_{n2} [/mm] = [mm] f_{n+k+3} [/mm]


Ich würde jetzt den linken Teil der Gleichung , also die Summe , so weit umformen , bis ich auf [mm] f_{n+k+3} [/mm] komme.
Kann ich für [mm] f_{k+1} f_{n+1} [/mm] die Annahme im IS übernehmen ? Oder macht das hier keinen Sinn ?


Bezug
                
Bezug
Fib. Zahl induktiv beweisen: Antwort
Status: (Antwort) fertig Status 
Datum: 17:47 So 08.12.2013
Autor: reverend

Hallo nochmal,

> unabhängig von meiner letzten Frage würde ich gerne
> trotzdem mit der Induktion weitermachen.
>  
> Induktionsanfang: sei n = 0

Hier nimmst Du doch richtig an: n=0, k=0.

>  Dann ist
> [mm]f_0 f_0[/mm] + [mm]f_1 f_1[/mm] = [mm]f_1[/mm]
>  1 = 1 .

Ok, erfüllt.

> Induktionsschritt:
>  Nehmen an , Aussage [mm]f_k f_n[/mm] + [mm]f_{k+1} f_{n+1}[/mm] = [mm]f_{n+k+1}[/mm]
> ist richtig für n,k  [mm]\in \IN[/mm]
>  
> Zu zeigen ist ; Aussage gilt auch für k+1 , n+1

Damit erledigst Du aber nicht alle Fälle, sondern letztlich nur alle, wo n=k ist.

Vom Ansatz her zeigst Du mehr, wenn Du beweist, dass die Aussage dann auch für k+1,n gilt. Da die Formel ja symmetrisch in k,n ist, hast Du damit dann gleichzeitig schon bewiesen, dass die Aussage auch für k,n+1 gilt. Und das reicht, um die komplette doppelte Induktion auf einmal zu erschlagen.

> [mm]f_{k+1} f_{n+1} +f_{k2}[/mm] + [mm]f_{n2}[/mm] = [mm]f_{n+k+3}[/mm]
>  
>
> Ich würde jetzt den linken Teil der Gleichung , also die
> Summe , so weit umformen , bis ich auf [mm]f_{n+k+3}[/mm] komme.

Das wird schwierig - und wie gesagt: falscher Ansatz!

>  Kann ich für [mm]f_{k+1} f_{n+1}[/mm] die Annahme im IS
> übernehmen ? Oder macht das hier keinen Sinn ?

Das macht nicht nur Sinn, sondern ist im Induktionsbeweis immer nötig. Wenn es nicht nötig wäre, bräuchte man keinen Induktionsbeweis.

Grüße
reverend

Bezug
                        
Bezug
Fib. Zahl induktiv beweisen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:51 So 08.12.2013
Autor: pc_doctor

Hallo , danke für die Antworten.

Ich schreibe es dann gleich nochmal auf und poste es dann hier , aber woran erkennt man , dass die Formel symmetrisch ist ?

Bezug
                                
Bezug
Fib. Zahl induktiv beweisen: Antwort
Status: (Antwort) fertig Status 
Datum: 17:55 So 08.12.2013
Autor: reverend

Hallo,

> Ich schreibe es dann gleich nochmal auf und poste es dann
> hier , aber woran erkennt man , dass die Formel symmetrisch
> ist ?

Vertausch mal n und k. Dann steht immer noch genau die gleiche Formel da.

Grüße
reverend


Bezug
                                        
Bezug
Fib. Zahl induktiv beweisen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:02 So 08.12.2013
Autor: pc_doctor

Stimmt , + ist kommutativ.

Okay , also , ich habs jetzt so:
IA:
Sei n=0 und k=0
[mm] f_0 f_0 [/mm] + [mm] f_1 f_1 [/mm] = [mm] f_1 [/mm]
1 = 1 , stimmt.

IS:
Nehmen an , Aussage [mm] f_k f_n [/mm] + [mm] f_{k+1} f_{n+1} [/mm] = [mm] f_{n+k+1} [/mm] ist richtig für n,k [mm] \in \IN [/mm]

Z.z. : Gilt für k+1 ,n (Stichwort "Symmetrie")

[mm] f_{k+1} f_n [/mm] + [mm] f_{k+2} f_{n+1} [/mm] = [mm] f_{n+k+2} [/mm]

So ab hier muss ich dann irgendwie umformen, aber ich sehe den Wald vor lauter Bäumen nicht.

Wie kann ich das umformen , bis ich die Annahme einsetzen kann , sodass ich am Ende auf [mm] f_{n+k+2} [/mm] komme.  

Bezug
                                                
Bezug
Fib. Zahl induktiv beweisen: Antwort
Status: (Antwort) fertig Status 
Datum: 22:11 So 08.12.2013
Autor: reverend

Hallo pc-doctor,

hier kommen wir zum Kern der Aufgabe und damit zum eigentlichen Problem.

Es scheint eine schier unerschöpfliche Fülle von Fibonacci-Aufgaben zu geben. Das ist immer irgendwie mühsam, aber ein paar Sachen haben sie gemeinsam. ;-)

> Stimmt , + ist kommutativ.

Ja, und die Multiplikation auch.

> Okay , also , ich habs jetzt so:
>  IA:
> Sei n=0 und k=0
>  [mm]f_0 f_0[/mm] + [mm]f_1 f_1[/mm] = [mm]f_1[/mm]
>  1 = 1 , stimmt.

Ist ok, aber Du wirst gleich sehen, dass das nicht reicht.

> IS:
> Nehmen an , Aussage [mm]f_k f_n[/mm] + [mm]f_{k+1} f_{n+1}[/mm] = [mm]f_{n+k+1}[/mm]
> ist richtig für n,k [mm]\in \IN[/mm]
>  
> Z.z. : Gilt für k+1 ,n (Stichwort "Symmetrie")
>  
> [mm]f_{k+1} f_n[/mm] + [mm]f_{k+2} f_{n+1}[/mm] = [mm]f_{n+k+2}[/mm]
>  
> So ab hier muss ich dann irgendwie umformen, aber ich sehe
> den Wald vor lauter Bäumen nicht.

Hier gibts auch reichlich Bäume.
Wo Du hin willst, ist ... [mm] \text{blabla}=f_{n+k}+f_{n+k+1}=f_{n+k+2} [/mm]

Das eine ist ja nett, also [mm] f_{n+k+1}. [/mm] Das kommt ja in der Induktionsvoraussetzung vor. Das Problem ist aber [mm] f_{n+k}. [/mm] Damit Du das auch darstellen kannst, wirst Du mehr als Induktionsanfang brauchen. Das ist bei Fibonacci immer so, wenn man Induktion anwenden will.

Das ist ja auch logisch. Sobald Du eine Rekursionsdarstellung von [mm] a_{n+1} [/mm] hast, in der nicht nur [mm] a_n, [/mm] sondern auch [mm] a_{n-1} [/mm] vorkommt, wirst Du einen doppelten Induktionsanfang brauchen. Hier also für n=k=0 und für n=0, k=1 oder umgekehrt (was ja das gleiche ist). Dann kriegst Du auch den Induktionsschritt hin.

Ansonsten braucht man außer dieser (doppelten) IV nur noch die rekursive Definition der Folgenglieder und ein ziemliches Geschick darin, die richtigen Teile der Formel mittels der Rekursion so zu zerlegen, dass man nur bekannte Fibonaccizahlen darin hat.

> Wie kann ich das umformen , bis ich die Annahme einsetzen
> kann , sodass ich am Ende auf [mm]f_{n+k+2}[/mm] komme.  

Tja, probiers mal. Es ist ein bisschen "tricky", aber es geht mit den Tipps oben.

Meld Dich mal mit einem Versuch.
Ach ja, der Induktionsschritt geht dann von $n+1$ zu $n+2$, aber das ändert ja nichts.

Grüße
reverend

Bezug
        
Bezug
Fib. Zahl induktiv beweisen: Antwort
Status: (Antwort) fertig Status 
Datum: 17:42 So 08.12.2013
Autor: reverend

Hallo pc-doctor,

irgendwie machst Du es Dir hier unnötig kompliziert.

> Sei [mm]f_i[/mm] die i-te Fibonacci-Zahl , also [mm]f_0[/mm] = 0 , [mm]f_1[/mm] = 1
> und [mm]f_n= f_{n-2}[/mm] + [mm]f_{n-1}[/mm] für n > 1
>  Beweisen Sie für beliebige n,k [mm]\ge[/mm] 0:
>  
> [mm]f_k f_n[/mm] + [mm]f_{k+1} f_{n+1}[/mm] = [mm]f_{n+k+1}[/mm]

>

>  Hallo , um erst mal diese rekursive Formel [mm]f_k f_n[/mm] +
> [mm]f_{k+1} f_{n+1}[/mm] = [mm]f_{n+k+1}[/mm] zu verstehen:

Die ist nicht rekursiv. Rekursiv ist hier nur das Bildungsgesetz der Fibonaccifolge; genau darum verwendest Du ja später auch vollständige Induktion.
  

> Sei n = 2 und k = 1.
>  
> =>
>  [mm]f_1 f_2[/mm] + [mm]f_2 f_3[/mm] = [mm]f_4[/mm]
>  
> [mm]f_1[/mm] ist 1 , [mm]f_2[/mm] ist = [mm]f_0[/mm] + [mm]f_1[/mm] , also 1
>  Also ist [mm]f_1 f_2[/mm] 1 ( wird nicht addiert ,oder ? )

Nein, da wird nichts mehr addiert, es ist doch eine ganz normale Multiplikation.

> Dann ist
>  
> [mm]f_2 f_3[/mm] , also [mm]f_2[/mm] ist [mm]f_0[/mm] + [mm]f_1[/mm] , also 1
>  [mm]f_3[/mm] ist [mm]f_1[/mm] + [mm]f_2 (f_2[/mm] ist 1 , [mm]f_1[/mm] ist 1 , also ) :
>  [mm]f_3[/mm] ist 2
>  Also habe ich für [mm]f_2 f_3[/mm] 1 und 2, welche davon nehme ich
> jetzt ?

Beide. Aus [mm] f_2=1 [/mm] und [mm] f_3=2 [/mm] folgt [mm] f_2f_3=1*2=2. [/mm]

> [mm]f_4[/mm] ist [mm]f_2[/mm] + [mm]f_3[/mm] , also 3
>  
> Würde erstmal diese komische Formel klären wollen..

Du hast das schon richtig verstanden.
Einfacher für dieses Beispiel: [mm] f_0=0, f_1=1, f_2=1, f_3=2, f_4=3 [/mm]
Dann einsetzen: [mm] f_1f_2+f_2f_3=1*1+1*2=3=f_4. [/mm] Fertig.

> Vielen Dank im Voraus.

Damit hast Du ja aber nur ein Beispiel geklärt.
Zeigen sollst Du, dass das für beliebige n,k gilt, also z.B. auch für [mm] f_{126}f_{439}+f_{127}f_{440}=f_{566}. [/mm]

Grüße
reverend

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis-Induktion"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorkurse.de
[ Startseite | Mitglieder | Teams | Forum | Wissen | Kurse | Impressum ]