Fibonaccifolge

24.10.2005, 01:51

Der Gast

Fibonaccifolge

Ein Thread noch, ist der letzte (versprochen)

Fibonacci Zahlen, angeblich ist:

F(n+1) = $\begin{eqnarray*} \sum_{k=0}^*~\begin{pmatrix} n-k \\ k \end{pmatrix} \end{eqnarray*}$

wobei $\begin{eqnarray*} *= [\frac{n}{2} ] \end{eqnarray*}$

(Gausklammer)

Wie beweise ich diese Identität?

24.10.2005, 07:55

Sciencefreak

Auf diesen Beitrag antworten »

Versuch es doch mal mit vollständiger Induktion, also für n=1 gilt das ganze doch noch und für n=2 auch. Dann müsste man vielleicht noch die rekursive Bildungsvorschrift kennen und dann sollte das ganze ungefähr hinkommen, habe den Beweis aber noch nicht durchgerechnet

24.10.2005, 11:55

Der Gast

Auf diesen Beitrag antworten »

Das hatte ich mir auch gedacht...

F(n-1) + F(n) = F(n+1)

Nur bin ich dadurch der Lösung nicht unbedingt näher gekommen (was mitunter am meisten ankotzt ist die Gausklammer).

24.10.2005, 11:57

4c1d

Auf diesen Beitrag antworten »

Tipp : Benutze im Induktionsschritt $\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} = \begin{pmatrix} n-1 \\ k-1 \end{pmatrix} + \begin{pmatrix} n-1 \\ k \end{pmatrix} \end{eqnarray*}$

edit : Der Gaußklammer dürfte bei $\begin{eqnarray*} n \in \mathbb{N} \end{eqnarray*}$ leicht mit einer Fallunterscheidung beizukommen sein.

24.10.2005, 12:19

Der Gast

Auf diesen Beitrag antworten »

Es ist mir nicht ganz klar wo ich das anbringen kann

24.10.2005, 12:46

4c1d

Auf diesen Beitrag antworten »

Ok, dann mache ich mal den Anfang :
Die Fibonacci-Zahlen sind rekursiv definiert als $\begin{eqnarray*} F_{n+1} =F_n + F_{n-1} \end{eqnarray*}$
Nach Induktionsvoraussetzung (den Induktionsanfang spare ich mir mal) ist also $\begin{eqnarray*} F_{n+1} = \sum_{k=0}^{[\frac{n-1}{2}]} \begin{pmatrix}n-1-k \\ k \end{pmatrix} + \sum_{k=0}^{[\frac{n-2}{2}]} \begin{pmatrix}n-2-k \\ k \end{pmatrix} \end{eqnarray*}$
Zu zeigen ist, dass das wiederum gleich $\begin{eqnarray*} \sum_{k=0}^{[\frac{n}{2}]} \begin{pmatrix}n-k \\ k \end{pmatrix} \end{eqnarray*}$ ist.

Um z.B. den letzten Term so umzuformen, dass man die Gleichheit sieht, könntest du den eben angesprochenen Satz in der Form $\begin{eqnarray*} \begin{pmatrix}n-k \\ k \end{pmatrix} = \begin{pmatrix}n-1-k \\ k-1 \end{pmatrix} + \begin{pmatrix}n-1-k \\ k\end{pmatrix} \end{eqnarray*}$ anwenden.

24.10.2005, 13:11

Der Gast

Auf diesen Beitrag antworten »

Gut das es FFF Studenten gibt Prost

24.10.2005, 13:19

Auf diesen Beitrag antworten »

Aber aufpassen an den "Summenrändern", d.h. bei $\begin{eqnarray*} k=0 \end{eqnarray*}$ und $\begin{eqnarray*} k=\left\lfloor \frac{n}{2} \right\rfloor \end{eqnarray*}$ ! Lehrer

24.10.2005, 13:27

4c1d

Auf diesen Beitrag antworten »

Zitat:

Gut das es FFF Studenten gibt

Danke, aber ich habe mit FFF nichts zu tun Augenzwinkern

24.10.2005, 13:55

Der Gast

Auf diesen Beitrag antworten »

Ich bin jetzt auf folgendes gekommen (beim ersten Fall, n gerade:

F(n+2)-F(n+1)= $\begin{eqnarray*} \sum_{k=0}^*~ \begin{pmatrix} n-k-2 \\ k \end{pmatrix} \end{eqnarray*}$

mit

$\begin{eqnarray*} *= [\frac{n}{2}] \end{eqnarray*}$

und es soll ja am Ende

F(n) = $\begin{eqnarray*} \sum_{k=0}^*~ \begin{pmatrix} n-k-1 \\ k \end{pmatrix} \end{eqnarray*}$

mit $\begin{eqnarray*} *= [\frac{n-1}{2}] \end{eqnarray*}$

Wie komme ich darauf?

24.10.2005, 15:09

Leopold

Auf diesen Beitrag antworten »

Von diesem ganzen Fallunterscheidungskram kann man sich ja befreien, wenn man sich klar macht, was eigentlich

$\begin{eqnarray*} \sum_{0 \leq k \leq \frac{n}{2}}^{}~{{n-k} \choose k} \end{eqnarray*}$

bedeutet. Das heißt doch:

Summiere, mit $\begin{eqnarray*} {n \choose 0} \end{eqnarray*}$ beginnend, Binomialkoeffizienten auf, von Summand zu Summand den oberen Eintrag um 1 verkleinernd, den unteren um 1 erhöhend, bis es nicht mehr geht:

$\begin{eqnarray*} {n \choose 0} + {{n-1} \choose 1} + {{n-2} \choose 2} + \ldots \end{eqnarray*}$

Das "bis es nicht mehr geht" heißt: solange alle Ausdrücke definiert sind. Da in einer Summe Summanden vom Wert 0 nicht stören, legen wir daher fest:

$\begin{eqnarray*} {n \choose k} := 0, \ \text{falls} \ k<0 \ \text{oder} \ k>n \end{eqnarray*}$

(Und das ist ja keine spontane Eingebung, sondern eine durchaus übliche Konvention: Das Pascalsche Dreieck wird zur Pascalschen Halbebene erweitert. Das Konstruktionsprinzip "Summe nebeneinander stehender Binomialkoeffizienten gibt den darunter auf Lücke stehenden Binomialkoeffizienten", siehe erste Formel bei 4c1d, gilt weiterhin.)

Dann kann man

$\begin{eqnarray*} F^{*}(n) := \sum_{0 \leq k \leq \frac{n}{2}}^{}~{{n-k} \choose k} = \sum_{k=-\infty}^{\infty}~{{n-k} \choose k} \end{eqnarray*}$

schreiben. Fast alle Summanden in der letzten Summe sind 0. Und die, die nicht 0 sind, sind dieselben wie in der ursprünglichen Definition. Und mit dieser zweiten Darstellung kann man bequem arbeiten.

Jetzt muß man nur

$\begin{eqnarray*} \text{(I)} \ \ F^{*}(0) = 1 \, , \ F^{*}(1) = 1 \end{eqnarray*}$
$\begin{eqnarray*} \text{(II)} \ \ F^{*}(n-1) + F^{*}(n) = F^{*}(n+1) \, , \ n \geq 1 \end{eqnarray*}$

zeigen. Dann haben die Folgen $\begin{eqnarray*} \left( F(n)\right )_{n \geq 0} \end{eqnarray*}$ und $\begin{eqnarray*} \left( F^{*}(n)\right )_{n \geq 0} \end{eqnarray*}$ dieselben Startwerte und gehorchen derselben Rekursionsvorschrift. Also müssen sie übereinstimmen.

Und $\begin{eqnarray*} \text{(II)} \end{eqnarray*}$ zeigt man, indem man mit der linken Seite beginnt, dort gemäß der Definition einsetzt, in der ersten Summe eine Indexverschiebung ( $\begin{eqnarray*} k \end{eqnarray*}$ durch $\begin{eqnarray*} k-1 \end{eqnarray*}$ ersetzen) durchführt und die bekannte Regel von der Pascalschen Halbebene verwendet. Dann steht alles schon da.

24.10.2005, 19:21

4c1d

Auf diesen Beitrag antworten »

Interessanter Ansatz, Leopold. Daran hatte ich garnicht gedacht.

@ Der Gast : Bei deiner Gleichung stimmt etwas nicht. Aber jetzt sollte es ja keine große Mühe mehr sein, den Beweis nochmal von Anfang an durchzuführen smile

Neue Frage »

Antworten »

Fibonaccifolge

Verwandte Themen