Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Beweise folgende Identität über Fibonacci Zahlen

Beweise folgende Identität über Fibonacci Zahlen

Universität / Fachhochschule

Erzeugende Funktionen

Tags: Diskrete Mathematik, Erzeugende Funktionen, Fibonacci - Zahlen, Identiät, Induktion

simssims aktiv_icon

16:47 Uhr, 15.05.2021

Hallo euch!

ich soll folgende Fibonacci Identität beweisen:

\sum_{k = 0}^{n} F_{k} F_{n - k} = \sum_{k = 0}^{n} (k + 1) F_{k + 1} (- 2)^{n - k}

Ich habe versucht es mit vollständige Induktion zu zeigen und bin bis hier

\sum_{k = 0}^{n + 1} F_{k} F_{n + 1 - k} = \sum_{k = 0}^{n} F_{k} F_{n + 1 - k} + F_{n + 1} = \sum_{k = 0}^{n} F_{k} (F_{n - k} + F_{n - k - 1}) + F_{n + 1} = \sum_{k = 0}^{n} F_{k} F_{n - k} + \sum_{k = 0}^{n} F_{k} F_{n - k - 1} + F_{n + 1}

gekommen aber kann nicht weiter gehen. Wir sind im Kapitel über erzeugende Funktionen aber ich kenne mich damit gar nicht aus, so wenn es mit Induktion geht, wäre es wunderbar, ansonsten wenn mir jemand bei die Methode mit erzeugende Funktionen es einfach erklären könnte, wäre das auch wunderbar.

Ich bedanke euch im Voraus für die Hilfe

LG

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

DrBoogie aktiv_icon

16:49 Uhr, 15.05.2021

Es war schon vor ein paar Tagen.
www.onlinemathe.de/forum/Fibonacci-Identitaet

Es geht vermutlich auch mit der Induktion, aber nur sehr lang und mühsam.
Und da das Thema sowieso erzeugende Funktionen sind, schlage ich vor, dass du das versuchst zu verstehen.

simssims aktiv_icon

18:30 Uhr, 15.05.2021

Hallo DrBoogie,

Vielen Dank! Sehr hilfreich. Ich wollte noch ein Paar Sachen klären. Du hast auf diese Antwort hingewiesen math.stackexchange.com/questions/3221920/proof-of-a-fibonacci-identity?rq=1.

Kannst du mir bitte diesen Teil erklären?

\sum_{n = 0}^{\infty} A_{n} z^{n} = \sum_{k = 0}^{\infty} (k + 1) F_{k + 1} z^{k} \times \sum_{j = 0}^{\infty} (- 2 z)^{j}

Wie genau folgt die Gleichheit und steht das

\times

für normales Multiplikation?

Und vielleicht eine mehr theoretische Frage, wieso betrachten wir überhaupt die unendliche Reihe

\sum_{n = 0}^{\infty} A_{n} z^{n}

?

Danke im Voraus

DrBoogie aktiv_icon

19:30 Uhr, 15.05.2021

"Kannst du mir bitte diesen Teil erklären?
∑n=0∞Anzn=∑k=0∞(k+1)Fk+1zk×∑j=0∞(−2z)j"

Rechts steht das Produkt von zwei Reihen. Wenn man die Cauchy-Formel für Produkte nutzt, kommt als Ergebnis das, was links steht.
de.wikipedia.org/wiki/Cauchy-Produktformel
Wie man darauf kommt, ist wie so oft schwer zu sagen. Aber wenn man die Cauchy-Formel kennt, dann wird man beim betrachten der Summe

\sum F_{k} F_{n - k}

schon auf die Idee kommen, dass hier irgendwo diese Formel benutzt werden soll. Das "riecht" sozusagen nach Cauchy-Formel. :-)

"Wie genau folgt die Gleichheit und steht das × für normales Multiplikation?"

Ja.

"Und vielleicht eine mehr theoretische Frage, wieso betrachten wir überhaupt die unendliche Reihe ∑n=0∞Anzn?"

Das ist die erzeugende Funktion für die Folge

A_{n}

. Und da wir

\sum F_{k} F_{n - k} = A_{n}

zeigen wollen, und zwar über die erzeugenden Funktionen, ist es naheliegend diese Reihe zu betrachten.

simssims aktiv_icon

19:32 Uhr, 15.05.2021

Super! Danke vielmals!

simssims aktiv_icon

22:12 Uhr, 16.05.2021

Ich hätte noch eine ganz kleine Rückfrage und zwar bei die erste Gleichheit ∑n=0∞Anzn=∑k=0∞(k+1)Fk+1zk×∑j=0∞(−2z)j. Warum haben wir diese Laufvariablen jetzt als k und j. Und was ist die Zusammenhang zwischen k,j und n. Ist k+j=n?

Danke im Voraus

DrBoogie aktiv_icon

22:21 Uhr, 16.05.2021

Du meinst das Produkt von zwei Reihen?
Also

(\sum_{k} (k + 1) F_{k + 1} z^{k}) \cdot (\sum_{j} (- 2 z)^{j})

?
Es gibt keinen Zusammenhang zwischen

k

und

j

, diese

k

und

j

sind nur Indizes in der Reihe, also nur Bezeichnungen.
Es könnte dort genauso gut

(\sum_{k} (k + 1) F_{k + 1} z^{k}) \cdot (\sum_{k} (- 2 z)^{k})

stehen oder auch

(\sum_{α} (α + 1) F_{α + 1} z^{α}) \cdot (\sum_{M} (- 2 z)^{M})

. Das wäre genau dasselbe. Die Indizes werden nur benutzt, um kurze Darstellung der Reihe zu bekommen und um nicht z.B.

(- 2 z)^{0} + (- 2 z)^{1} + (- 2 z)^{2} + . . .

schreiben zu müssen.

DrBoogie aktiv_icon

22:24 Uhr, 16.05.2021

"was ist die Zusammenhang zwischen k,j und n. Ist k+j=n?"

Du hast eine Reihe über

n

und dann ein Produkt von zwei Reihen mit Indizes

j

und

k

.
Was soll denn

k + j = n

überhaupt bedeuten?

k, j

und

n

nehmen doch unendlich viele Werte.

k + j = n

ist einfach sinnlos in diesem Kontext. Du kannst Indizes einer Reihe nicht außerhalb der Reihe betrachten, sie sind in der Reihe gebunden.

simssims aktiv_icon

22:27 Uhr, 16.05.2021

Okay aber wieso dann darf ich es teilen, und warum darf ich den

z^{k}

bei beide Faktoren nehmen. Und warum nehmen wir z.B nicht auch den (-2) mit?
Da ich hätte gedacht dass wir irgendwie den linken Teil "teilen"? Aber warum kommt dann diese z^k bei beide?
Ich habe den Artikel über die Cauchy Produkt gesehen, aber kann irgenwie nicht den Zusammenhang machen, ich übersehe sicher etwas.

DrBoogie aktiv_icon

22:33 Uhr, 16.05.2021

Wir teilen doch gar nichts.
Es wird einfach die Cauchy-Formel benutzt.
Nach ihr ist der

n

-te Summand der Produktreihe

\sum_{k = 0}^{n} a_{k} b_{n - k}

, wo

a_{k}

aus einer Reihe kommt und

b_{n - k}

aus der zweiten Reihe.
In unserem Fall also

a_{k} = (k + 1) F_{k + 1} z^{k}

und

b_{n - k} = (- 2 z)^{n - k}

.
Das ergibt also die Summe

\sum_{k = 0}^{n} (k + 1) F_{k + 1} z^{k} (- 2 z)^{n - k} = \sum_{k = 0}^{n} (k + 1) F_{k + 1} z^{k} z^{n - k} (- 2)^{n - k} = \sum_{k = 0}^{n} (k + 1) F_{k + 1} z^{n} (- 2)^{n - k}

. Fertig.

Wenn du Probleme hast, die Cauchy-Formel zu verstehen, dann berechne zuerst die ersten ein paar Terme der Reihe. Also zuerst was beim Produkt bei der

0

-ter Potenz von

z

steht, dann was bei der ersten Potenz usw.

simssims aktiv_icon

22:34 Uhr, 16.05.2021

Ist es diese Teil von Cauchy Produkt bei Multiplikation von Potenzreihen, oder?

DrBoogie aktiv_icon

22:35 Uhr, 16.05.2021

Verstehe die Frage nicht.
Cauchy-Produkt gilt allgemein, nicht nur für Potenzreihen.

simssims aktiv_icon

22:35 Uhr, 16.05.2021

Habe es verstanden, war nur verwirrt.

Herzlichen dank!

1535999

1535868

	Status: nicht eingeloggt	Noch nicht registriert?