Fibonacci Beweis < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
Mal wieder die guten, alten Fibonacci Zahlen. Diesmal in der Form
[mm] F_{n+1}=\summe_{k=0}^{n}\vektor{n-k \\ k}
[/mm]
Und dann soll ein Beweis her. Tippe mal auf die vollst. Induktion, aber mir will irgendwie kein Ansatz gelingen......
Kann mir jemand helfen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:11 Sa 13.11.2004 | | Autor: | Micha |
Hallo!
> Mal wieder die guten, alten Fibonacci Zahlen. Diesmal in
> der Form
>
> [mm]F_{n+1}=\summe_{k=0}^{n}\vektor{n-k \\ k}
[/mm]
>
> Und dann soll ein Beweis her. Tippe mal auf die vollst.
> Induktion, aber mir will irgendwie kein Ansatz
> gelingen......
>
Vollständige Induktion klingt sehr gut. Vielleicht sammeln wir erstmal, was wir dafür alles brauchen. Induktionsanfang, Induktionsschritt... mit Induktionsvoraussetzung und Induktionsbeweis. Ok 1. Schritt:
Induktionsanfang: n=0 , n=1
[mm] $F_0 [/mm] = 1 $
[mm] $\summe_{k=0}^{0}\vektor{0-k \\ k} [/mm] = [mm] \vektor{0 \\ 0} [/mm] = 1$
[mm] $F_1 [/mm] = 1$
[mm] $\summe_{k=0}^{1}\vektor{1-k \\ k} [/mm] = [mm] \vektor{1-0 \\ 0} [/mm] + [mm] \vektor{1-1 \\ 1}= \vektor{1 \\ 0} [/mm] + [mm] \vektor{0 \\ 1} [/mm] = 1 + 0 = 1$
Die Anfangsbedingungen stimmen also. Nun können wir den Induktionsbeweis über 2 Elemente durchführen:
Induktionsschritt: $n, n+1 [mm] \to [/mm] n+1, n+2$
Induktionsvoraussetzung: Die Behauptung gilt für ein n und n+1. Dann gilt für n+2:
Induktionsbehauptung:
[mm] $F_{n+2} [/mm] = [mm] \summe_{k=0}^{n+2}\vektor{n+2-k \\ k}$
[/mm]
Beweis:
[mm]F_{n+2} = F_n + F_{n+1} \underbrace{=}_{Ivor} \summe_{k=0}^{n}\vektor{n-k \\ k} + \summe_{k=0}^{n+1}\vektor{n+1-k \\ k}= \dots [/mm]
Kommst du jetzt weiter?
Gruß Micha 
|
|
|
| |
|
Noch nicht ganz, weil ich die Regeln für das [mm] \vektor{x \\ y} [/mm] nicht kenne. Würde sagen, dass ich aus der zweiten Summe das n+1 ziehe, oder?
Also: ... [mm] \underbrace{=}_{Richtig?} \summe_{k=0}^{n}\vektor{n-k \\ k} [/mm] + [mm] \summe_{k=0}^{n}\vektor{n+1-k \\ k} [/mm] + [mm] \vektor{n+2-n+1 \\ n+1} [/mm] = [mm] (\summe_{k=0}^{n}\vektor{n-k \\ k} [/mm] + [mm] \vektor{n+1-k \\ k}) [/mm] + [mm] \vektor{3 \\ n+1} \underbrace{=}_{???}
[/mm]
Kann auch total falsch sein......
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:46 So 14.11.2004 | | Autor: | Micha |
Hallo nochmal!
> Noch nicht ganz, weil ich die Regeln für das [mm]\vektor{x \\ y}[/mm]
> nicht kenne. Würde sagen, dass ich aus der zweiten Summe
> das n+1 ziehe, oder?
>
> Also: ... [mm]\underbrace{=}_{Richtig?} \summe_{k=0}^{n}\vektor{n-k \\ k}[/mm]
> + [mm]\summe_{k=0}^{n}\vektor{n+1-k \\ k}[/mm] + [mm]\vektor{n+2-n+1 \\ n+1}[/mm]
> = [mm](\summe_{k=0}^{n}\vektor{n-k \\ k}[/mm] + [mm]\vektor{n+1-k \\ k})[/mm]
> + [mm]\vektor{3 \\ n+1} \underbrace{=}_{???}
[/mm]
>
> Kann auch total falsch sein......
>
Hmm ich glaub du hast beim Hinausziehen des letzten Summanden einen kleinen Fehler gemacht, oder ich kann den Schritt einfach nicht ganz nachvollziehen:
[mm] \summe_{k=0}^{n}\vektor{n-k \\ k} + \summe_{k=0}^{n}\vektor{n+1-k \\ k} + \vektor{n+1-(n+1) \\ n+1}[/mm]
[mm]= \summe_{k=0}^{n}\vektor{n-k \\ k} + \summe_{k=0}^{n}\vektor{n+1-k \\ k}+ \underbrace{\vektor{0 \\ n+1}}_{=0}[/mm]
Weiter weiß ich jetzt auch erstmal nich.. :(
Gruß Micha
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:22 So 14.11.2004 | | Autor: | Hanno |
Hallo!
Ja, du hast einen Fehler bei der Entfernung des letzten Gliedes gemacht. Du kannst es aber auch gleich weglassen, da es gleich Null ist.
Es ergibt sich also:
[mm] $\summe_{k=0}^{n}{\vektor{n-k\\ k}}+\summe_{k=0}^{n+1}{\vektor{n+1-k\\ k}}=\summe_{k=0}^{n}{\left( \vektor{n-k\\ k}+\vektor{n+1-k\\ k} \right)}=\summe_{k=0}^{n}{\left( \frac{(n-k)!}{k!\cdot (n-k-k)!}+\frac{(n+1-k)!}{k!\cdot (n+1-k-k)!}\right)}$
[/mm]
[mm] $=\summe_{k=0}^{n}{\left( \frac{(n-k)!\cdot (n+1-2k)}{k!(n+1-2k)!}+\frac{(n+1-k)!}{k!\cdot (n+1-2k)!} \right)}=\summe_{k=0}^{n}{\left( \frac{(n-k)!\cdot (n+1-2k)+(n+1-k)!}{k!\cdot (n+1-2k)!} \right) }$
[/mm]
Betrachten wir unser Ziel, nämlich den Term [mm] $\vektor{n+2-k\\ k}=\frac{(n+2-k)!}{k!\cdot (n+2-2k)!}$ [/mm] in der Summe, so sehen wir, dass wir den Bruch noch mit $(n+2-2k)$ erweitern müssen. Dies ergibt:
[mm] $=\summe_{k=0}^{n}{\left( \frac{(n+2-2k)\cdot \left( (n-k)!\cdot (n+1-2k+n+1-k) \right)}{k!\cdot (n+2-2k)!} \right) }=\summe_{k=0}^{n}{\left( \frac{(n+2-2k)\cdot \left( (n-k)!\cdot (2n+2-3k) \right)}{k!\cdot (n+2-2k)!} \right) }=\summe_{k=0}^{n}{\left( \frac{ (n-k)!\cdot (n+2-2k)\cdot(2n+2-3k)}{k!\cdot (n+2-2k)!} \right) }$
[/mm]
So, und wenn ich bis hier keinen Rechenfehler gemacht habe, dann scheint es nicht zu stimmen, da [mm] $(n+2-2k)\cdot(2n+2-3k)=(n+1-k)(n+2-k)$ [/mm] gelten müsste, was aber nicht stimmt nach meinen Rechnungen.
Liebe Grüße,
Hanno
|
|
|
| |
|
Hmm, ein Fehler habe ich schon entdeckt....(wahrscheinlich):
[mm] \summe_{k=0}^{n}{\left( \frac{(n-k)!}{k!\cdot (n-k-k)!}+\frac{(n+1-k)!}{k!\cdot (n+1-k-k)!}\right)} =\summe_{k=0}^{n}{\left( \frac{(n-k)!\cdot (n+1-2k)}{k!(n+1-2k)!}+\frac{(n+1-k)!}{k!\cdot (n+1-2k)!} \right)}= [/mm] (...)
Wieso erweiterst Du mit (n+1-2k) im ersten Bruch? Es steht doch schon (n-k-k) da?
|
|
|
| |
|
Habe nun endlich die Aufgabe gelöst, dieser Schritt
[mm] F_{n+2} [/mm] = [mm] F_n [/mm] + [mm] F_{n+1} \underbrace{=}_{Ivor} \summe_{k=0}^{n}\vektor{n-k \\ k} [/mm] + [mm] \summe_{k=0}^{n+1}\vektor{n+1-k \\ k}= \dots
[/mm]
ist leider falsch, weshalb die Rechnung weiter unten dann nicht aufgeht. Es muss heißen:
[mm] F_{n+2} [/mm] = [mm] F_n [/mm] + [mm] F_{n+1} \underbrace{=}_{Ivor} \summe_{k=0}^{n-1}\vektor{n-1-k \\ k} [/mm] + [mm] \summe_{k=0}^{n}\vektor{n-k \\ k}= \dots [/mm]
Und dann kommt man mit vielen Umformungen zur Lösung.
Gruß, misterbecks
|
|
|
|
