Fibonacci mit Binominalkoeffi. < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:04 Do 28.05.2009 | | Autor: | Pille456 |
| Aufgabe | Es gilt: [mm] F_{n+1}=\sum_{k=0}^{[\frac{n-1}{2}]}{n-k\choose k}.
[/mm]
Beweis
Folgt sofort via Induktion aus [mm] ${n\choose k}={n-1\choose k}+{n-1\choose k-1}$. [/mm] |
Hi,
Den Satz oben habe ich auf einer Internetseite gefunden, die das Thema behandelt. Induktionsbeweis sollte doch machbar sein, dachte ich mir. Jedoch komme ich momentan nicht weiter:
IA: n = 0 oder n = 1 (klar)
IS: n = n+1
$ [mm] F_{n+1}=\sum_{k=0}^{[\frac{n-1}{2}]}{n-k\choose k}. [/mm] = [mm] F_{n}+F_{n-1}\gdw \sum_{k=0}^{[\frac{n-1}{2}]}{n-k\choose k} [/mm] = [mm] \sum_{k=0}^{[\frac{n-2}{2}]}{n-1-k\choose k} [/mm] + [mm] \sum_{k=0}^{[\frac{n-3}{2}]}{n-2-k\choose k}.
[/mm]
Nun dachte ich mir, dass ich zwei Fälle unterscheide:
1. Fall [mm] [\bruch{n-3}{2}] [/mm] = [mm] [\bruch{n-2}{2}] [/mm] = a [mm] \Rightarrow[\bruch{n-1}{2}]= [/mm] a+1
2. Fall a-1 = [mm] [\bruch{n-3}{2}] [/mm] < [mm] [\bruch{n-2}{2}] [/mm] = a [mm] \Rightarrow[\bruch{n-1}{2}]= [/mm] a
(wobei [] hier ![[]](/images/popup.gif) gaußsche Klammern sein sollen)
1. Fall: [mm] \sum_{k=0}^{a+1}{n-k\choose k} [/mm] = [mm] \sum_{k=0}^{a}{n-1-k\choose k} [/mm] + [mm] \sum_{k=0}^{a}{n-2-k\choose k}. [/mm]
2. Fall [mm] \sum_{k=0}^{a}{n-k\choose k} [/mm] = [mm] \sum_{k=0}^{a}{n-1-k\choose k} [/mm] + [mm] \sum_{k=0}^{a-1}{n-2-k\choose k}.
[/mm]
So nun habe ich hier zwei ganze Zettel voll mit Umformungen aber keine fruchtet so recht.. Vielleicht hat jemand von euch einen Ansatz?
|
|
| |
|
> Es gilt:
> [mm]F_{n+1}=\sum_{k=0}^{[\frac{n-1}{2}]}{n-k\choose k}.[/mm]
>
> Beweis
> Folgt sofort via Induktion aus [mm]{n\choose k}={n-1\choose k}+{n-1\choose k-1}[/mm].
> Hi,
> Den Satz oben habe ich auf einer Internetseite gefunden,
> die das Thema behandelt. Induktionsbeweis sollte doch
> machbar sein, dachte ich mir. Jedoch komme ich momentan
> nicht weiter:
> IA: n = 0 oder n = 1 (klar)
> IS: n = n+1
> $ [mm]F_{n+1}=\sum_{k=0}^{[\frac{n-1}{2}]}{n-k\choose k}.[/mm] =
> [mm]F_{n}+F_{n-1}\gdw \sum_{k=0}^{[\frac{n-1}{2}]}{n-k\choose k}[/mm]
> = [mm]\sum_{k=0}^{[\frac{n-2}{2}]}{n-1-k\choose k}[/mm] +
> [mm]\sum_{k=0}^{[\frac{n-3}{2}]}{n-2-k\choose k}.[/mm]
Hallo,
Wie lautet denn eigentlich Deine Induktionsvoraussetzung?
im Induktionsschluß willst Du doch beweisen, daß die Aussage auch für n+1 gilt.
Die im Induktionsschluß zu zeigende Aussage lautet also: [mm] F_{(n+1)+1}=\sum_{k=0}^{[\frac{(n+1)-1}{2}]}{(n+1)-k\choose k}.
[/mm]
Gruß v. Angela
> Nun dachte
> ich mir, dass ich zwei Fälle unterscheide:
> 1. Fall [mm][\bruch{n-3}{2}][/mm] = [mm][\bruch{n-2}{2}][/mm] = a
> [mm]\Rightarrow[\bruch{n-1}{2}]=[/mm] a+1
> 2. Fall a-1 = [mm][\bruch{n-3}{2}][/mm] < [mm][\bruch{n-2}{2}][/mm] = a
> [mm]\Rightarrow[\bruch{n-1}{2}]=[/mm] a
> (wobei [] hier
> gaußsche Klammern
> sein sollen)
>
>
> 1. Fall: [mm]\sum_{k=0}^{a+1}{n-k\choose k}[/mm] =
> [mm]\sum_{k=0}^{a}{n-1-k\choose k}[/mm] +
> [mm]\sum_{k=0}^{a}{n-2-k\choose k}.[/mm]
> 2. Fall [mm]\sum_{k=0}^{a}{n-k\choose k}[/mm] =
> [mm]\sum_{k=0}^{a}{n-1-k\choose k}[/mm] +
> [mm]\sum_{k=0}^{a-1}{n-2-k\choose k}.[/mm]
>
> So nun habe ich hier zwei ganze Zettel voll mit Umformungen
> aber keine fruchtet so recht.. Vielleicht hat jemand von
> euch einen Ansatz?
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 13:28 Do 28.05.2009 | | Autor: | Pille456 |
> Hallo,
>
> Wie lautet denn eigentlich Deine Induktionsvoraussetzung?
>
> im Induktionsschluß willst Du doch beweisen, daß die
> Aussage auch für n+1 gilt.
>
> Die im Induktionsschluß zu zeigende Aussage lautet also:
> [mm]F_{(n+1)+1}=\sum_{k=0}^{[\frac{(n+1)-1}{2}]}{(n+1)-k\choose k}.[/mm]
>
> Gruß v. Angela
[mm] F_{n+2} [/mm] = [mm] \sum_{k=0}^{[\frac{(n+1)-1}{2}]}{(n+1)-k\choose k} [/mm] = [mm] F_{n+1}+F_{n}
[/mm]
Soweit klar, nur bis n+1 habe ich es ja gar nicht bewiesen. Ich beweise es doch nur für alle Zahlen bis einschließlich n(d.h. ob die Formel für [mm] F_{n+1} [/mm] gilt weiss ich noch garnicht). Aber okay, wenn ich z.B. n+1 = b setzen würde und dann alles über b beweise, würde sich ja am grundlegenden Beweis nichts ändern, außer ein paar Buchstaben. Also so wirklich weiter komme ich da nicht oder übersehe ich hier gerade etwas?
|
|
|
| |
|
> > Hallo,
> >
> > Wie lautet denn eigentlich Deine Induktionsvoraussetzung?
> >
> > im Induktionsschluß willst Du doch beweisen, daß die
> > Aussage auch für n+1 gilt.
> >
> > Die im Induktionsschluß zu zeigende Aussage lautet also:
> > [mm]F_{(n+1)+1}=\sum_{k=0}^{[\frac{(n+1)-1}{2}]}{(n+1)-k\choose k}.[/mm]
>
> >
> > Gruß v. Angela
>
> [mm]F_{n+2}[/mm] = [mm]\sum_{k=0}^{[\frac{(n+1)-1}{2}]}{(n+1)-k\choose k}[/mm]
> = [mm]F_{n+1}+F_{n}[/mm]
> Soweit klar, nur bis n+1 habe ich es ja gar nicht
> bewiesen. Ich beweise es doch nur für alle Zahlen bis
> einschließlich n(d.h. ob die Formel für [mm]F_{n+1}[/mm] gilt weiss
> ich noch garnicht).
Hallo,
nun hast Du immer noch nicht verraten, wie Deine induktionsvoraussetzung lautet...
Aber egal, denn demnach, was Du schreibst, bekomme ich den Eindruck, daß Du das Prinzip der vollständigen Induktion nicht richtig verstanden hast:
man hat eine Aussage, die für alle n zu beweisen ist.
I.A.: man rechnet vor, daß sie für ein konkretes n gilt, meist für n=0 oder n=1.
I.V.: man nimmt an, daß die Aussage für ein n gilt. ("Nimmt an" , nichts mit "noch nicht bewiesen", darauf kommt mir's an.)
I.S.: man zeigt, daß sie unter dieser Voraussetzung auch für die darauffolgende Zahl n+1 gilt.
Vielleicht hast Du Dich aber nur ungeschickt ausgedrückt .
Was Du getan hast, verstehe ich jetzt: Du hast die Behauptung für [mm] F_n [/mm] formuliert und arbeitest damit, weil Dir das bequemer ist.
Gut. Ich mache in etwa da weiter, wo Du aufgehört hast:
[mm] F_{n+1}=F_n+F_{n-1}=$ \sum_{k=0}^{a}{n-1-k\choose k} [/mm] $ + $ [mm] \sum_{k=0}^{a}{n-2-k\choose k}. [/mm] $ =$ [mm] \sum_{k=0}^{a}{n-1-k\choose k} [/mm] $ + $ [mm] \sum_{k=1}^{a+1}{n-2-(k-1)\choose k-1}. [/mm] $ =$ [mm] \sum_{k=0}^{a}{n-1-k\choose k} [/mm] $ + $ [mm] \sum_{k=1}^{a+1}{n-1-k \choose k-1}. [/mm] $ =$ [mm] \sum_{k=1}^{a}({n-1-k\choose k} [/mm] $ + $ {n-1-k [mm] \choose [/mm] k-1})$ [mm] +{n-1\choose } [/mm] $ +{n-1-(a [mm] +1)\choose [/mm] (a+1)-1}
Zu zeigen
> 1. Fall: $ [mm] \sum_{k=0}^{a+1}{n-k\choose k} [/mm] $ = $ [mm] \sum_{k=0}^{a}{n-1-k\choose k} [/mm] $ + $ [mm] \sum_{k=0}^{a}{n-2-k\choose k}. [/mm] $
EDIT: Ich hab' das hier voll versemmelt. Vielleicht komme ich am späten Abend noch dazu.
Gruß v. Angela
Aber okay, wenn ich z.B. n+1 = b setzen
> würde und dann alles über b beweise, würde sich ja am
> grundlegenden Beweis nichts ändern, außer ein paar
> Buchstaben. Also so wirklich weiter komme ich da nicht oder
> übersehe ich hier gerade etwas?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:36 Do 28.05.2009 | | Autor: | Pille456 |
Hm mir scheint da ist was beim Formelsystem falsch gelaufen. Naja ich hab mal mit dem Ansatz weiter gemacht, habe aber noch einen kleinen Knackpunkt:
[mm] F_{n+1}=F_n+F_{n-1}= \sum_{k=0}^{a}{n-1-k\choose k} [/mm] + [mm] \sum_{k=0}^{a}{n-2-k\choose k} =\sum_{k=0}^{a}{n-1-k\choose k}+\sum_{k=1}^{a+1}{n-2-(k-1)\choose k-1} [/mm] = [mm] 1+\sum_{k=1}^{a}{n-1-k\choose k}+\sum_{k=1}^{a+1}{n-1-k)\choose k-1} [/mm] = [mm] 1+\sum_{k=1}^{a}{n-1-k\choose k}+\sum_{k=1}^{a}{n-1-k)\choose k-1}+{n-1-(a+1)\choose a+1-1} [/mm] = [mm] 1+\sum_{k=1}^{a}({n-1-k\choose k}+{n-1-k)\choose k-1})+{n-1-a-1)\choose a} [/mm] = [mm] 1+\sum_{k=1}^{a}{n-k\choose k}+{n-a-2)\choose a}=\sum_{k=0}^{a}{n-k\choose k}+{n-a-2)\choose a}
[/mm]
Nun muss ich nur noch den letzten Summand wieder in das Summenzeichen "reinziehen" und schon hätte ich meine Lösung. Aber irgendwie passt das nicht so ganz.
|
|
|
| |
|
> Hm mir scheint da ist was beim Formelsystem falsch
> gelaufen. Naja ich hab mal mit dem Ansatz weiter gemacht,
> habe aber noch einen kleinen Knackpunkt:
>
> [mm]F_{n+1}=F_n+F_{n-1}= \sum_{k=0}^{a}{n-1-k\choose k}[/mm] +
> [mm]\sum_{k=0}^{a}{n-2-k\choose k} =\sum_{k=0}^{a}{n-1-k\choose k}+\sum_{k=1}^{a+1}{n-2-(k-1)\choose k-1}[/mm]
> = [mm]1+\sum_{k=1}^{a}{n-1-k\choose k}+\sum_{k=1}^{a+1}{n-1-k)\choose k-1}[/mm]
> = [mm]1+\sum_{k=1}^{a}{n-1-k\choose k}+\sum_{k=1}^{a}{n-1-k)\choose k-1}+{n-1-(a+1)\choose a+1-1}[/mm]
> = [mm]1+\sum_{k=1}^{a}({n-1-k\choose k}+{n-1-k)\choose k-1})+{n-1-a-1)\choose a}[/mm]
> = [mm]1+\sum_{k=1}^{a}{n-k\choose k}+{n-a-2)\choose a}=\sum_{k=0}^{a}{n-k\choose k}+{n-a-2)\choose a}[/mm]
>
> Nun muss ich nur noch den letzten Summand wieder in das
> Summenzeichen "reinziehen" und schon hätte ich meine
> Lösung. Aber irgendwie passt das nicht so ganz.
Hallo,
nachdem ich nun auch viel gerechnet habe, habe ich sinnigerweise mal ein Experiment gemacht und geguckt, ob die Behauptung überhaupt stimmt.
Sie stimmt nicht.
Wenn Du für n=1,2,3 rechnest, stellst Du schonmal fest, daß die Fibonaccizahl 2 ausfällt,
Für n=6 bekommt man $ [mm] \sum_{k=0}^{[\frac{6-1}{2}]}{6-k\choose k} [/mm] $=$ [mm] \sum_{k=0}^{[\frac{6-1}{2}]}{6-k\choose k} [/mm] $=$ [mm] \sum_{k=0}^{2}{6-k\choose k} [/mm] $=$ [mm] {6\choose 0}+{5\choose 1} +{4\choose 2} [/mm] $=1+5+6=12, und das ist gar keine Fibonaccizahl. Der Beweis kann also nicht klappen.
Wahrscheinlich stimmt die Behauptung, daß $ [mm] F_{n+1}=\sum_{k=0}^{[\frac{n}{2}]}{n-k\choose k}. [/mm] $, hab' ich jetzt aber keine Lust nachzurechnen.
Gruß v. Angela
|
|
|
|
