Fibonacci-Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:46 Fr 21.10.2016 | | Autor: | Attila |
Hallo,
ich hätte folgende Frage:
In der VL sollen wir zeigen, dass die Summe über Binomialkoeffizienten der (n+1)-ten Fibonaccizahl entspricht.
Ich will also die Formel [mm] $\sum_{k=0}^n \vektor{n-k \\ k}=a_{n+1}$ [/mm] beweisen. Es ist hier von [mm] $a_{n+1}$ [/mm] die Rede, da bei uns die Zahlen mit [mm] $a_1=1$ [/mm] beginnen, während mancher es wohl mit [mm] $a_0=1$ [/mm] startet, was dann [mm] $Formel=a_n$ [/mm] bedeuten würde.
Jedenfalls will ich den Induktionsschritt machen und dazu nachweisen, dass die Summe [mm] $a_n+a_{n+1}=a_{n+2}$ [/mm] ergibt, allerdings scheitere ich daran die Summen bzw. die Binmoialkoeffizienten passend umzuformen, damit die Summe aufgeht. Ich wäre daher für eure Hilfe dankbar.
Viele Grüße,
Attila
|
|
| |
|
Hiho,
offensichtlich ist $ [mm] \sum_{k=0}^{n+1} \binom{n-k}{k} [/mm] = [mm] \sum_{k=0}^{n} \binom{n-k}{k} [/mm] = [mm] \sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} \binom{n-k}{k}$ [/mm] (warum?)
Nutze nun die Identität
[mm] ${\binom {n+1}{k}}={\binom {n}{k-1}}+{\binom {n}{k}}$
[/mm]
Damit erhältst du:
[mm] $\binom{n+1-k}{k} [/mm] = [mm] \binom{n-k}{k-1} [/mm] + [mm] \binom{n-k}{k}$
[/mm]
Und damit:
$ [mm] \sum_{k=0}^{n+1} \binom{n+1-k}{k}$
[/mm]
$= 1 + [mm] \sum_{k=1}^{n+1} \binom{n+1-k}{k}$
[/mm]
$= 1 + [mm] \sum_{k=1}^{n+1} \binom{n-k}{k-1} [/mm] + [mm] \sum_{k=1}^{n+1} \binom{n-k}{k} [/mm] $
$= 1 + [mm] \sum_{k=1}^{n+1} \binom{n-k}{k-1} [/mm] + [mm] \sum_{k=1}^{n} \binom{n-k}{k} [/mm] $
$= [mm] \sum_{k=0}^{n} \binom{n-k}{k} [/mm] + [mm] \sum_{k=1}^{n+1} \binom{n-k}{k-1} [/mm] $
$= [mm] a_{n+1} [/mm] + [mm] \sum_{k=0}^{n} \binom{n-k-1}{k} [/mm] $
$= [mm] a_{n+1} [/mm] + [mm] \sum_{k=0}^{n-1} \binom{n-k-1}{k}$
[/mm]
$= [mm] a_{n+1} [/mm] + [mm] a_{n}$
[/mm]
Gruß,
Gono
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:30 Fr 21.10.2016 | | Autor: | Attila |
Vielen Dank, jetzt habe ich es verstanden. Zu deiner Frage, das müsste gelten, weil für die entsprechenden Binomialkoeffizienten gilt n-k<k, womit der Koeffizient qua Definition 0 wird.
Gruß,
Attila
|
|
|
|
