Summendarstellung der Fibonacci Zahlne

Da bin ich wieder. Die Aufgabe kann tatsächlich etwas ungemütlich werden. Aber ich habe mir ein paar Gedanken gemacht:

1. Die Formel lautet $\begin{eqnarray*} F_{n+1}=\sum_{l=0}^{\left\lfloor \frac n 2 \right\rfloor}\binom{n-l}{l} \end{eqnarray*}$ .
Ich möchte die Formel aber so umstellen, dass sie für $\begin{eqnarray*} n\in\mathbb{N}_0 \end{eqnarray*}$ funktioniert und mir dabei ausgibt $\begin{eqnarray*} F_0=1, F_1=1, F_2=2,... \end{eqnarray*}$ (vorher gab sie aus $\begin{eqnarray*} F_1=1,F_2=1,F_3=2 \end{eqnarray*}$ ).
Also ändere ich sie erstmal so: $\begin{eqnarray*} F_n=\sum_{l=0}^{\left\lfloor \frac n 2 \right\rfloor}\binom{n-l}{l} \end{eqnarray*}$ .

2. Eine wichtige Beobachtung: Das letzte Glied der Summe lautet, d.h. der letzte Summand, $\begin{eqnarray*} \binom{n-\left\lfloor\frac n 2 \right\rfloor}{\left\lfloor \frac n 2 \right\rfloor}=\binom{\left\lceil \frac n 2 \right\rceil}{\left\lfloor \frac n 2 \right\rfloor} \end{eqnarray*}$ .
So, wenn wir nun die Summe "verlängern" würden, das heißt ein $\begin{eqnarray*} l>\left\lfloor\frac n 2 \right\rfloor \end{eqnarray*}$ annehmen würden, dann ergäbe sich folgendes:
Zum einen $\begin{eqnarray*} l\geq \left\lfloor\frac n 2 \right\rfloor +1 \end{eqnarray*}$ (da die Laufindizes natürlich sind, ist der nächstsgrößere eben der +1) und somit sofort als neuer letzter Summand $\begin{eqnarray*} \binom{\left\lceil\frac n 2\right\rceil -1 }{\left\lfloor\frac n 2 \right\rfloor +1} \end{eqnarray*}$ , das ist jedoch Null, für alle $\begin{eqnarray*} n\in\mathbb{N} \end{eqnarray*}$ .
Das heißt wir können unsere Summe beliebig verlängern und so in die einfachere Darstellung $\begin{eqnarray*} f_n=\sum_{l=0}^{n}\binom{n-l}{l} \end{eqnarray*}$ umwandeln.

3. Dies lässt sich recht geradlinig per Induktion beweisen, wenn man $\begin{eqnarray*} \binom{-1}{x} \end{eqnarray*}$ mit $\begin{eqnarray*} x>-1 \end{eqnarray*}$ als Null auffasst. Zumindest war das bei mir notwendig. Vielleicht geht es auch ohne diese (möglicherweise etwas ungewöhnliche Konvention).

Wie ich schon sagte, tolle Aufgabe.

29.10.2009, 09:32

Mystic

Auf diesen Beitrag antworten »

Mein Gott, wären nur alle Beziehungen für Fibonaccizahlen so leicht zu "sehen" wie diese... traurig

Zunächst einmal sieht man sofort, dass

$\begin{eqnarray*} F_{n+1} =\sum_{l=0}^{\lfloor n/2 \rfloor} \binom {n-l} l \end{eqnarray*}$

für n=-1 (leere Summe!) und n=0 tatsächlich erfüllt ist... Um zu sehen, warum der Ausdruck auf der rechten Seite die Rekursionsbeziehung für Fibonacczahlen, nämlich

$\begin{eqnarray*} F_{n+1} = F_n + F_{n-1} \quad (n \ge 1) \end{eqnarray*}$

erfüllt, solltest du einfach mal einige Werte für aufeinanderfolgende n ansehen, z.B.

$\begin{eqnarray*} \begin{array}{llllllll} n=6: &&& \binom 6 0 +& \binom 5 1 +& \binom 4 2 +& \binom 3 3 \\[.2cm] n=7: && \binom 7 0 +& \binom 6 1 +& \binom 5 2 +& \binom 4 3 \\[.2cm]n=8: && \binom 8 0 +& \binom 7 1 +& \binom 6 2 +& \binom 5 3 +&\binom 4 4 \end{array}\\ \end{eqnarray*}$

$\begin{eqnarray*} \begin{array}{llllllll} n=7: && \binom 7 0 +& \binom 6 1 +& \binom 5 2 +& \binom 4 3 \\[.2cm]n=8: & \binom 8 0 +& \binom 7 1 +& \binom 6 2 +& \binom 5 3 +&\binom 4 4 \\[.2cm] n=9: & \binom 9 0 +& \binom 8 1 +& \binom 7 2 +& \binom 6 3 +&\binom 5 4 \end{array}\\ \end{eqnarray*}$

und konsequent die Beziehung

$\begin{eqnarray*} \binom n {k-1} +\binom n k = \binom {n+1} k \end{eqnarray*}$

einsetzen... Wenn es dann noch nicht "klick" macht...

29.10.2009, 09:39

Manus

Auf diesen Beitrag antworten »

Edit:

War Unfug. Hab's rausgenommen um keinen zu verwirren.

29.10.2009, 14:30

temporär

Auf diesen Beitrag antworten »

Hallo,
kannst deinen Gedanken mal bitte weiterführen und dabei eine Erläuterung beschreiben. Wäre nett wenn diese auch "normalsterbliche" verstehen würden ;-)
Bzw. expliziet was die zweite Formel damit zu tun hat.

Danke

29.10.2009, 15:54

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von temporär
Hallo,
kannst deinen Gedanken mal bitte weiterführen und dabei eine Erläuterung beschreiben. Wäre nett wenn diese auch "normalsterbliche" verstehen würden ;-)
Bzw. expliziet was die zweite Formel damit zu tun hat.

Danke

Hm, bin mir jetzt nicht sicher, ob das an mich gerichtet war...Selbst wenn, hab ich ja oben schon alles gesagt, aber wenn es hilft, dann betrachten wir einfach dazu nochmals in aller Ausführlichkeit eines der beiden Beispiele, nämlich

Zitat:

Original von Mystic
$\begin{eqnarray*} \begin{array}{llllllll} n=6: &&& \binom 6 0 +& \binom 5 1 +& \binom 4 2 +& \binom 3 3 \\[.2cm] n=7: && \binom 7 0 +& \binom 6 1 +& \binom 5 2 +& \binom 4 3 \\[.2cm]n=8: && \binom 8 0 +& \binom 7 1 +& \binom 6 2 +& \binom 5 3 +&\binom 4 4 \end{array}\\ \end{eqnarray*}$

Unter Verwendung der Formel

$\begin{eqnarray*} \binom n {k-1} +\binom n k = \binom {n+1} k \end{eqnarray*}$

sieht man dass sich die 3.Zeile gerade als Summe der 1. und 2.Zeile ergibt, wobei ich die Summanden genau so untereinander geschrieben habe, dass man diese Formel schön anwenden kann, also

$\begin{eqnarray*} \binom 60 +\binom 61= \binom 71,\quad \binom 51 +\binom 52= \binom 62,\quad \binom 42 +\binom 43= \binom 53 \end{eqnarray*}$

während dies für den "Rand" wegen

$\begin{eqnarray*} \binom 70 = \binom 80, \quad \binom 33 = \binom 44 \end{eqnarray*}$

trivialerweise gilt...

30.10.2009, 17:34

Bobbie

Auf diesen Beitrag antworten »

Zitat:

Original von jester. und somit sofort als neuer letzter Summand $\begin{eqnarray*} \binom{\left\lceil\frac n 2\right\rceil -1 }{\left\lfloor\frac n 2 \right\rfloor +1} \end{eqnarray*}$ , das ist jedoch Null, für alle $\begin{eqnarray*} n\in\mathbb{N} \end{eqnarray*}$ .

Hab ich was falsch verstanden oder ist das falsch?

für n= 5 kommt da bei mir 1 raus

30.10.2009, 22:00

jester.

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \binom{\left\lceil\frac 5 2 \right\rceil -1}{\left\lfloor \frac 5 2 \right \rfloor +1} = \binom{3-1}{2+1}=\binom{2}{3}=0 \end{eqnarray*}$

30.10.2009, 22:16

Auf diesen Beitrag antworten »

@jester

Da vielen nur die "Fakultätsdefinition" des Binomialkoeffizienten geläufig ist, sollte mal noch dazu gesagt werden, dass dies auf der allgemeineren Definition

$\begin{eqnarray*} \binom{x}{k} := \frac{1}{k!} \prod_{j=0}^{k-1} (x-j) \end{eqnarray*}$

für beliebige reelle Zahlen $\begin{eqnarray*} x \end{eqnarray*}$ und natürliche Zahlen $\begin{eqnarray*} k \end{eqnarray*}$ beruht (im Fall k=0 ist das "leere" Produkt wie sonst auch üblich gleich 1 zu setzen).

30.10.2009, 22:22

jester.

Auf diesen Beitrag antworten »

So geht es natürlich auch. Ich kenne das einfach als Konvention $\begin{eqnarray*} \binom n k = 0,\text{ falls }k>n \end{eqnarray*}$ , was ja dann auch wieder der Anzahl der Möglichkeiten entspricht, k Elemente aus n zu ziehen. Es gibt eben nicht so wahnsinnig viele Möglichkeiten, 3 aus 2 Elementen zu ziehen. Augenzwinkern

30.10.2009, 22:24

Auf diesen Beitrag antworten »

In dem Zusammenhang:

Zitat:

Original von jester.
wenn man $\begin{eqnarray*} \binom{-1}{x} \end{eqnarray*}$ mit $\begin{eqnarray*} x>-1 \end{eqnarray*}$ als Null auffasst. Zumindest war das bei mir notwendig. Vielleicht geht es auch ohne diese (möglicherweise etwas ungewöhnliche Konvention).

Wirklich ungewöhnlich - im Sinne der gerade von mir genannten erweiterten Defintion ist nämlich ganz im Gegenteil dazu $\begin{eqnarray*} \binom{-1}{k} = (-1)^k \end{eqnarray*}$ für alle natürlichen Zahlen $\begin{eqnarray*} k \end{eqnarray*}$ . Augenzwinkern

So muss die Defintion übrigens lauten, wenn man will, dass die binomische Reihe

$\begin{eqnarray*} (1+x)^{\alpha} = \sum_{k=0}^{\infty} \binom{\alpha}{k} x^k \end{eqnarray*}$

auch wirklich so stimmt...

30.10.2009, 22:38

jester.

Auf diesen Beitrag antworten »

Dass es an dieser Stelle haken könnte, war mir klar. Aber ich wollte $\begin{eqnarray*} f_n=\sum_{l=0}^{n}\binom{n-l}{l} \end{eqnarray*}$ durch Induktion zeigen, und im Induktionsschritt mit $\begin{eqnarray*} n+1 \end{eqnarray*}$ sind dann, beim Aufteilen des Binomialkoeffizienten (mit der üblichen Rekursion) diese ganzen fiesen Teile $\begin{eqnarray*} \binom{-1}{...} \end{eqnarray*}$ aufgetaucht, von denen eines übrig geblieben ist, wenn ich das richtig im Kopf habe. Daher habe ich diese Annahme getroffen und der Beweis ging wunderbar auf.

Aber vielleicht sollte ich auf diese Stelle noch mal einen Blick werfen... Big Laugh

31.10.2009, 17:01

temporär

Auf diesen Beitrag antworten »

Hallo,
danke erstmal, hat mir schon viel gebracht. Die logische Verbindung habe ich jetzt auch entdecken können. Nur für den Beweis fehlt mir jetzt der Ansatz.
Wie kann ich rechnerrisch zeigen das die Summendarstellung der Fibonacci-Zahlen mit der in der induzierten Formel vom Pascalschen Dreieck zusammen hängt?

Danke,
mfg

31.10.2009, 17:36

fibo

Auf diesen Beitrag antworten »

Hi!
Wenn ich den Beweis per Induktion über die rekursive Definition der Fibonaccizahlen angehe, stellt sich mir die Frage, ob und wie ich die zwei Summen zusammenfassen kann:
$\begin{eqnarray*} F_{n + 1} + F_{n} = \sum_{l=0}^{[\frac{n}{2}]}\binom{n - l}{l} + \sum_{l=0}^{[\frac{n - 1}{2}]}\binom{n - l - 1}{l} \end{eqnarray*}$
Für ein ungerades n ließen sich die Summen ja zusammenfassen, aber für ein gerades n sehe ich hierbei keinen Weg. Könnt ihr mir da weiterhelfen?
Nach einer Indexverschiebung in der ersten Summe, bin ich dann komplett ratlos, wie ich diese Summen zusammenfassen soll: $\begin{eqnarray*} \sum_{l=1}^{[\frac{n + 1}{2}]}\binom{n - l - 1}{l - 1} + \sum_{l=0}^{[\frac{n - 1}{2}]}\binom{n - l - 1}{l} \end{eqnarray*}$
Nach dem Zusammenfassen der Summen ließen sich die beiden Terme ja dann zum gewollten $\begin{eqnarray*} \binom{n - l}{l} \end{eqnarray*}$ zusammenfassen.

01.11.2009, 08:27

Mystic

Auf diesen Beitrag antworten »

Tja, sagen wir mal so, du bist schon an der Aufgabe

$\begin{eqnarray*} n-(l-1) \end{eqnarray*}$

im Zusammenhang mit der Indexverschiebung korrekt zu berechnen kläglich gescheitert... traurig

Im übrigen würde ich mir an deiner Stelle eines meiner früheren Postings hier noch einmal genau ansehen, wo ich exemplarisch für gerades und ungerades n dargestellt habe, wie man richtig zusammenfaßt... Die Übertragung auf den allgemeinen Fall sollte dann ja wohl ein Kinderspiel sein... Wink

01.11.2009, 12:51

temporär

Auf diesen Beitrag antworten »

Hallo,
mir fehlt nur noch ein schritt zur lösung ;-)
Ich habe nun die Formel in die Definition für Fibonacci eingesetzt und aufgelöst. Jetzt stehe ich genau an dem Punkt der Fallunterscheidung. Ich brauche eigentlich nur eine Antwort. Warum unterscheidet man an dem Punkt ob n gerade oder ungerade ist? Also ich meine was macht da den unterschied sodass man dies tun muss. Es ist eigentlich nur noch ein logisches Problem gerade.
Danke schonmal!

02.11.2009, 14:10

Mystic

Auf diesen Beitrag antworten »

Sozusagen auf vielfachen Wunsch, nachfolgend ganz allgemein nochmals die Fallunterscheidung für gerades und ungerades n... Ich habe dazu die rechte Seite der zu beweisenden Gleichung

$\begin{eqnarray*} F_{n+1} = \sum_{l=0}^{[n/2]} \binom {n-l}l \end{eqnarray*}$

mal vorläufig mit $\begin{eqnarray*} \tilde F_{n+1} \end{eqnarray*}$ bezeichnet...

Der Anfang ist noch für beide Fälle gleich, nämlich

$\begin{eqnarray*} \tilde F_{n + 1} + \tilde F_{n} = \sum_{l=0}^{[\frac n2]}\binom{n - l}l + \sum_{l=0}^{[\frac{n - 1}2]}\binom{n - l - 1}l=\sum_{l=0}^{[\frac n2]}\binom{n - l}l + \sum_{l=1}^{[\frac{n-1}2]+1}\binom{n - l }{l-1} \end{eqnarray*}$

Aber dann kommt eine Fallunterscheidung, nämlich

1. Fall: n gerade, daher ist

$\begin{eqnarray*} \left \lfloor{\frac{n-1}2}\right \rfloor+1=\left \lfloor{\frac n2} \right \rfloor,\quad \left \lfloor{\frac {n+1}2} \right \rfloor=\left \lfloor{\frac n2} \right \rfloor \end{eqnarray*}$

und es geht oben weiter mit

$\begin{eqnarray*} \tilde F_{n + 1} + \tilde F_{n}=\binom n 0 +\sum_{l=1}^{[\frac n2]}\left(\binom {n-l} l+\binom{n - l }{l-1} \right)=\binom {n+1}0+\sum_{l=1}^{[\frac n2]}\binom {n-l+1}l =\sum_{l=0}^{[\frac {n+1}2]}\binom {(n+1)-l}l =\tilde F_{n+2} \end{eqnarray*}$

2. Fall: n ungerade, daher ist

$\begin{eqnarray*} \left \lfloor{\frac{n-1}2}\right \rfloor=\left \lfloor{\frac n2} \right \rfloor,\quad \left \lfloor{\frac {n+1}2} \right \rfloor=\left \lfloor{\frac n2} \right \rfloor+1 \end{eqnarray*}$

und es geht oben weiter mit

$\begin{eqnarray*} \tilde F_{n + 1} + \tilde F_{n}=\binom n 0 +\sum_{l=1}^{[\frac n2]}\left(\binom {n-l} l+\binom{n - l }{l-1} \right)+\binom{[ \frac n2]}{[ \frac n2]}=\binom {n+1}0+\sum_{l=1}^{[\frac n2]}\binom {n-l+1}l +\binom{[ \frac {n+1}2]}{[ \frac {n+1}2]}=\sum_{l=0}^{[\frac {n+1}2]}\binom {(n+1)-l}l =\tilde F_{n+2} \end{eqnarray*}$

Da außerdem

$\begin{eqnarray*} F_0 =\tilde F_0, \quad F_1 =\tilde F_1 \end{eqnarray*}$

wie schon früher ausgeführt wurde, gilt somit tatächlich ganz allgemein

$\begin{eqnarray*} \forall n \in \mathbb N:\tilde F_n=F_n, \text{ q.e.d.} \end{eqnarray*}$

03.11.2009, 00:13

asda

Auf diesen Beitrag antworten »

Zitat:

Original von Mystic

und es geht oben weiter mit

$\begin{eqnarray*} \tilde F_{n + 1} + \tilde F_{n}=\binom n 0 +\sum_{l=1}^{[\frac n2]}\left(\binom {n-l} l+\binom{n - l }{l-1} \right)+\binom{[ \frac n2]}{[ \frac n2]}=\binom {n+1}0+\sum_{l=1}^{[\frac n2]}\binom {n-l+1}l +\binom{[ \frac {n+1}2]}{[ \frac {n+1}2]}=\sum_{l=0}^{[\frac {n+1}2]}\binom {(n+1)-l}l =\tilde F_{n+2} \end{eqnarray*}$
[/latex]

Kann mir das jemand nochmal genauer erklären? ich verstehe das nicht, vor allem wo kommt dieses Binom $\begin{eqnarray*} \binom{[ \frac n2]}{[ \frac n2]}] \end{eqnarray*}$ her??Sonst kann ich soweit folgen.

03.11.2009, 08:36

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von asda

Zitat:

Schau dir dazu einfach noch einmal dieses Beispiel an, wo mit den Bezeichnungen des Beweises n=7, d.h., n ungerade ist (Achtung: Die oberste Zeile entspricht $\begin{eqnarray*} \tilde F_7 \end{eqnarray*}$ , die zweite Zeile $\begin{eqnarray*} \tilde F_{7+1} \end{eqnarray*}$ , die unterste Zeile schließlich $\begin{eqnarray*} \tilde F_{7+2} \end{eqnarray*}$ , d.h., der Index ist um 1 noch oben verschoben gegenüber der Beschriftung am linken Rand!)

Zitat:

Das Binom $\begin{eqnarray*} \binom{[ \frac n2]}{[ \frac n2]} \end{eqnarray*}$ entsprich dabei genau dem Binom $\begin{eqnarray*} \binom 33 \end{eqnarray*}$ rechts oben, das nach dem Aufsummieren der beiden Zeilen zu dem Binom $\begin{eqnarray*} \binom 44 \end{eqnarray*}$ wird...

Neue Frage »

Antworten »

Summendarstellung der Fibonacci Zahlne

Verwandte Themen