Fibonacci Folge < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:21 Mo 28.03.2011 | | Autor: | Mandy_90 |
| Aufgabe | | Die Fibonacci-Folge ist rekursiv definiert als die Folge [mm] f_{1}=f_{2}=1, f_{n+2}=f_{n}+f_{n+1}. [/mm] Man beweise [mm] \summe_{k=0}^{n} \vektor{n-k \\ k}=f_{n+1} [/mm] und erläutere dieses Ergebnis anhand des Pascalschen Dreiecks. |
Guten Abend^^
Ich habe mich an den Beweis gewagt, aber komme nicht mehr weiter.
Zuerst hab ich mich mit ein paar Beispielen vergewissert, ob das auch so stimmt. Ich hab versucht es mit vollständiger Induktion nach n zu beweisen:
IA: n=1: 1=1, gelingt.
IV: Angen. Beh. gilt für n.
IS: n [mm] \to [/mm] n+1: zu zeigen: [mm] \summe_{k=0}^{n+1} \vektor{n+1-k \\ k}=f_{n+2}=f_{n+1}+f_{n}.
[/mm]
Dann wollte ich den Summanden für n+1 rausziehen,dieser ist [mm] \vektor{0 \\ n+1}, [/mm] aber der ist gar nicht definiert. Was mach ich denn nun?
Vielen Dank
lg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:51 Mo 28.03.2011 | | Autor: | ullim |
Hi,
[mm] \vektor{n \\ k}=0 [/mm] für k>n per Definition s. ![[]](/images/popup.gif) hier
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:17 Mo 04.04.2011 | | Autor: | Mandy_90 |
> Hi,
>
> [mm]\vektor{n \\ k}=0[/mm] für k>n per Definition s.
> hier
Achso ok. Ich komme jetzt aber nicht mehr beim Induktionsschritt weiter.
Ich habe [mm] \summe_{k=0}^{n+1} \vektor{n+1-k \\ k}=\summe_{k=0}^{n} \vektor{n+1-k \\ k}+0=\summe_{k=0}^{n} \vektor{n+1-k \\ k}.
[/mm]
Ich versteh grad nicht wie ich jetzt weitermachen kann. Hat jemand einen Tipp für mich?
Vielen Dank
lg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:40 Mo 04.04.2011 | | Autor: | fred97 |
Zeigen sollst Du doch:
[mm] \sum_{k=0}^{\left\lfloor \frac n 2 \right\rfloor}\binom{n-k}{k}= f_{n+1}
[/mm]
Summiert wird bist [mm] \left\lfloor \frac n 2 \right\rfloor [/mm] !!!
FRED
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:58 Mo 04.04.2011 | | Autor: | Mandy_90 |
>
>
> Zeigen sollst Du doch:
>
> [mm]\sum_{k=0}^{\left\lfloor \frac n 2 \right\rfloor}\binom{n-k}{k}= f_{n+1}[/mm]
>
> Summiert wird bist [mm]\left\lfloor \frac n 2 \right\rfloor[/mm]
> !!!
>
> FRED
Steh ich jetzt voll auf dem Schlauch oder was ist los? Wieso bis n/2? In der Aufgabe steht, dass ich zeigen soll: [mm] \summe_{k=0}^{n} \vektor{n-k \\ k}=f_{n+1}
[/mm]
lg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:10 Mo 04.04.2011 | | Autor: | ullim |
Hi,
setze mal für k Werte grösser als [mm] \left[\bruch{n}{2}\right] [/mm] in [mm] \binom{n-k}{k} [/mm] ein, dann weisst Du wieso Du nur bis [mm] \left[\bruch{n}{2}\right] [/mm] summieren musst, berücksichtige mein erstes Post.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:16 Di 05.04.2011 | | Autor: | Mandy_90 |
> Hi,
>
> setze mal für k Werte grösser als
> [mm]\left[\bruch{n}{2}\right][/mm] in [mm]\binom{n-k}{k}[/mm] ein, dann
> weisst Du wieso Du nur bis [mm]\left[\bruch{n}{2}\right][/mm]
> summieren musst, berücksichtige mein erstes Post.
Achsoooo, jetzt hab ichs.Also ich gehe jetzt mit vollständiger Induktion an die Sache.
IA gelingt schonmal.
IV: Beh. gilt für n.
IS: n --> n+1:
zz: [mm] \summe_{k=0}^{\bruch{n+1}{2}} \vektor{n+1-k \\ k}=f_{n+2}.
[/mm]
Dann hab ich den Summand für [mm] k=\bruch{n+1}{2} [/mm] rausgezogen und habe
[mm] \summe_{k=0}^{\bruch{n+1}{2}} \vektor{n+1-k \\ k}=\summe_{k=0}^{} \vektor{n+1-k \\ k}+\vektor{\bruch{n+1}{2} \\ \bruch{n+1}{2}}=\summe_{k=0}^{} \vektor{n+1-k \\ k}+1.
[/mm]
Es ist [mm] 1=f_{1}=f_{2}.
[/mm]
Ich weiß jetzt nicht genau, bis wo ich aufsummieren muss,wenn ich den Summand für [mm] k=\bruch{n+1}{2} [/mm] rausziehe.
Stimmt das so bis hierhin?
Vielen Dank
lg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:29 Di 05.04.2011 | | Autor: | statler |
Mahlzeit,
ich schlage folgende Vorgehensweise vor:
[mm] (f_i) [/mm] ist deine Fibonacci-Folge. [mm] (g_i) [/mm] sei die durch [mm] g_i [/mm] := [mm] \summe_{k=0}^{i} \vektor{n-k \\ k} [/mm] definierte Folge.
Die mit vollständiger Induktion zu beweisende Aussage A(n) ist dann
A(n) = [mm] (g_{n-1} [/mm] = [mm] f_{n}) \wedge (g_{n} [/mm] = [mm] f_{n+1})
[/mm]
Jetzt ist A(1) klar durch Nachrechnen.
Also bleibt A(n) --> A(n+1).
A(n) bedeutet das, was oben steht. Wir berechnen [mm] g_{n+1}:
[/mm]
[mm] g_{n+1} [/mm] = [mm] \summe_{k=0}^{n+1} \vektor{n+1-k \\ k} [/mm] = [mm] \vektor{n+1 \\ 0} [/mm] + [mm] \summe_{k=1}^{n} \vektor{n+1-k \\ k} [/mm] = [mm] \vektor{n \\ 0} [/mm] + [mm] \summe_{k=1}^{n} \vektor{n-k+1 \\ k} [/mm] = [mm] \vektor{n \\ 0} [/mm] + [mm] \summe_{k=1}^{n} \vektor{n-k \\ k} [/mm] + [mm] \summe_{k=1}^{n} \vektor{n-k \\ k-1} [/mm] (Additionssatz für Binomialkoeffizienten, Pascalsches Dreieck) = [mm] \summe_{k=0}^{n} \vektor{n-k \\ k} [/mm] + [mm] \summe_{k=0}^{n-1} \vektor{n-1-k \\ k} [/mm] = [mm] g_n [/mm] + [mm] g_{n-1} [/mm] (nach Def. von g) = [mm] f_{n+1} [/mm] + [mm] f_n [/mm] (nach Induktionsvorauss.) = [mm] f_{n+2} [/mm] (nach Def. von Fibonacci).
Also [mm] (g_{n} [/mm] = [mm] f_{n+1}) \wedge (g_{n+1} [/mm] = [mm] f_{n+2}) [/mm] = A(n+1) qed
Viele Grüße aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:58 Do 07.04.2011 | | Autor: | Mandy_90 |
> Mahlzeit,
>
> ich schlage folgende Vorgehensweise vor:
>
> [mm](f_i)[/mm] ist deine Fibonacci-Folge. [mm](g_i)[/mm] sei die durch [mm]g_i[/mm] :=
> [mm]\summe_{k=0}^{i} \vektor{n-k \\ k}[/mm] definierte Folge.
> Die mit vollständiger Induktion zu beweisende Aussage
> A(n) ist dann
> A(n) = [mm](g_{n-1}[/mm] = [mm]f_{n}) \wedge (g_{n}[/mm] = [mm]f_{n+1})[/mm]
> Jetzt ist A(1) klar durch Nachrechnen.
>
> Also bleibt A(n) --> A(n+1).
> A(n) bedeutet das, was oben steht. Wir berechnen [mm]g_{n+1}:[/mm]
> [mm]g_{n+1}[/mm] = [mm]\summe_{k=0}^{n+1} \vektor{n+1-k \\ k}[/mm] =
> [mm]\vektor{n+1 \\ 0}[/mm] + [mm]\summe_{k=1}^{n} \vektor{n+1-k \\ k}[/mm] =
> [mm]\vektor{n \\ 0}[/mm] + [mm]\summe_{k=1}^{n} \vektor{n-k+1 \\ k}[/mm] =
> [mm]\vektor{n \\ 0}[/mm] + [mm]\summe_{k=1}^{n} \vektor{n-k \\ k}[/mm] +
> [mm]\summe_{k=1}^{n} \vektor{n-k \\ k-1}[/mm] (Additionssatz für
> Binomialkoeffizienten, Pascalsches Dreieck) =
> [mm]\summe_{k=0}^{n} \vektor{n-k \\ k}[/mm] + [mm]\summe_{k=0}^{n-1} \vektor{n-1-k \\ k}[/mm]
> = [mm]g_n[/mm] + [mm]g_{n-1}[/mm] (nach Def. von g) = [mm]f_{n+1}[/mm] + [mm]f_n[/mm] (nach
> Induktionsvorauss.) = [mm]f_{n+2}[/mm] (nach Def. von Fibonacci).
> Also [mm](g_{n}[/mm] = [mm]f_{n+1}) \wedge (g_{n+1}[/mm] = [mm]f_{n+2})[/mm] =
> A(n+1) qed
Vielen Dank statler. Eine Frage hab ich noch,wieso ist [mm] \summe_{k=1}^{n} \vektor{n-k \\ k}=\summe_{k=0}^{n} \vektor{n-k \\ k} [/mm] ? Wieso darf man jetzt einfach bei k=0 anfangen? Und wieso ist [mm] \summe_{k=1}^{n} \vektor{n-k \\ k-1}=\summe_{k=0}^{n-1} \vektor{n-1-k \\ k}, [/mm] müsste es nicht [mm] \summe_{k=1}^{n} \vektor{n-k \\ k-1}=\summe_{k=0}^{n-1} \vektor{n-1-k \\ k-1} [/mm] sein? Nach welchem Gesetz hast du das so umgeformt?
lg
|
|
|
| |
|
Hallo Mandy_90,
> > Mahlzeit,
> >
> > ich schlage folgende Vorgehensweise vor:
> >
> > [mm](f_i)[/mm] ist deine Fibonacci-Folge. [mm](g_i)[/mm] sei die durch [mm]g_i[/mm] :=
> > [mm]\summe_{k=0}^{i} \vektor{n-k \\ k}[/mm] definierte Folge.
> > Die mit vollständiger Induktion zu beweisende Aussage
> > A(n) ist dann
> > A(n) = [mm](g_{n-1}[/mm] = [mm]f_{n}) \wedge (g_{n}[/mm] = [mm]f_{n+1})[/mm]
> > Jetzt ist A(1) klar durch Nachrechnen.
> >
> > Also bleibt A(n) --> A(n+1).
> > A(n) bedeutet das, was oben steht. Wir berechnen
> [mm]g_{n+1}:[/mm]
> > [mm]g_{n+1}[/mm] = [mm]\summe_{k=0}^{n+1} \vektor{n+1-k \\ k}[/mm] =
> > [mm]\vektor{n+1 \\ 0}[/mm] + [mm]\summe_{k=1}^{n} \vektor{n+1-k \\ k}[/mm] =
> > [mm]\vektor{n \\ 0}[/mm] + [mm]\summe_{k=1}^{n} \vektor{n-k+1 \\ k}[/mm] =
> > [mm]\vektor{n \\ 0}[/mm] + [mm]\summe_{k=1}^{n} \vektor{n-k \\ k}[/mm] +
> > [mm]\summe_{k=1}^{n} \vektor{n-k \\ k-1}[/mm] (Additionssatz für
> > Binomialkoeffizienten, Pascalsches Dreieck) =
> > [mm]\summe_{k=0}^{n} \vektor{n-k \\ k}[/mm] + [mm]\summe_{k=0}^{n-1} \vektor{n-1-k \\ k}[/mm]
> > = [mm]g_n[/mm] + [mm]g_{n-1}[/mm] (nach Def. von g) = [mm]f_{n+1}[/mm] + [mm]f_n[/mm] (nach
> > Induktionsvorauss.) = [mm]f_{n+2}[/mm] (nach Def. von Fibonacci).
> > Also [mm](g_{n}[/mm] = [mm]f_{n+1}) \wedge (g_{n+1}[/mm] = [mm]f_{n+2})[/mm] =
> > A(n+1) qed
>
> Vielen Dank statler. Eine Frage hab ich noch,wieso ist
> [mm]\summe_{k=1}^{n} \vektor{n-k \\ k}=\summe_{k=0}^{n} \vektor{n-k \\ k}[/mm]
> ? Wieso darf man jetzt einfach bei k=0 anfangen? Und wieso
> ist [mm]\summe_{k=1}^{n} \vektor{n-k \\ k-1}=\summe_{k=0}^{n-1} \vektor{n-1-k \\ k},[/mm]
> müsste es nicht [mm]\summe_{k=1}^{n} \vektor{n-k \\ k-1}=\summe_{k=0}^{n-1} \vektor{n-1-k \\ k-1}[/mm]
> sein? Nach welchem Gesetz hast du das so umgeformt?
Hier ist eine Indexverschiebung durchgeführt worden.
Setze zunächst l=k-1, dann ist k=l+1, demnach
[mm]\summe_{k=1}^{n} \vektor{n-k \\ k-1}=\summe_{l=0}^{n-1} \vektor{n-(l+1) \\ (l+1)-1}=\summe_{l=0}^{n-1} \vektor{n-l-1 \\ l}=\summe_{k=0}^{n-1} \vektor{n-k-1 \\ k}[/mm]
>
> lg
Gruss
MathePower
|
|
|
|
