Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Fibonacci-Zahlen

Fibonacci-Zahlen

Universität / Fachhochschule

Folgen und Reihen

Tags: Folgen und Reihen

anonymous

18:28 Uhr, 24.10.2016

Aufgabenstellung:
In der Vorlesung wurden die Fibonacci-Zahlen

F_{n}, n \geq 0

eingeführt. Sie sind rekursiv definiert durch

F_{n + 1} = F_{n} + F_{n - 1}

mit

F_{0} = 0

und

F_{1} = 1

.

Zeigen Sie

F_{n + 1} = \sum_{i = 0}^{n} (\begin{matrix} n - i \\ i \end{matrix})

Mein Ansatz: Beweis durch Induktion

(IA)

n = 0

F_{1} = \sum_{i = 0}^{0} (\begin{matrix} 0 - i \\ i \end{matrix}) = (\begin{matrix} 0 \\ 0 \end{matrix}) = 1

(IS)

n \to n + 1

F_{n + 2} = \sum_{i = 0}^{n + 1} (\begin{matrix} n + 1 - i \\ i \end{matrix}) = \sum_{i = 0}^{n} (\begin{matrix} n - i \\ i \end{matrix}) + (\begin{matrix} n + 1 - (n + 1) \\ n + 1 \end{matrix})

Das Problem ist leider, dass dieser Schritt keinen Sinn ergibt, da

(\begin{matrix} n + 1 - (n + 1) \\ n + 1 \end{matrix}) = (\begin{matrix} 0 \\ n + 1 \end{matrix}) = 0

ist.

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

michaL aktiv_icon

18:53 Uhr, 24.10.2016

Hallo,

dein Versuch der Rückführung auf die Induktionsannahme ist recht einfallslos und zudem falsch.
Wenn, dann müsste es

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

heißen. (Beachte die vergessene +1 im Binomialkoeffizienten in der zweiten Summe!)

Wie du ganz recht bemerkst, sollte

(\binom{0}{n + 1}) = 0

gelten. Allerdings solltest du dann schon früher bemängeln, dass etwa die Hälfte der in der Summe angegebenen Binomialkoeffizienten gleich Null ist, nämlich immer dann, wenn

k

größer wird als

n - k

.
Das ist aber nicht das Problem.
1. Der Binomialkoeffizient

(\binom{n}{k})

kann getrost als Null betrachtet werden für

n < k

oder

n, k < 0

.
2. Wegen der vergessenen +1 (siehe oben) führt deine Idee sowieso nicht weit.

Du musst also eine andere "Rückführung" finden.
Verwende:

(\binom{n + 1}{k + 1}) = (\binom{n}{k}) + (\binom{n}{k + 1})

(bzw. sinngemäße Formel(n))

Mfg Michael

anonymous

19:41 Uhr, 24.10.2016

Ich komme einfach nicht darauf, wie ich

(\begin{matrix} n + 1 \\ k + 1 \end{matrix}) = (\begin{matrix} n \\ k + 1 \end{matrix}) + (\begin{matrix} n \\ k \end{matrix})

verwenden soll.

ledum aktiv_icon

20:20 Uhr, 24.10.2016

Hallo
1. musst du die Und Vors für 0 und 1 zeigen.
2. musst du für die Induktion vors dass die Formel für

n

und

n - 1

richtig ist, daraus dann dass sie für

n + 1

richtig ist. was du machst kann ja nicht zum Erfolg führen,, da du die Def. der Fibonnaci
ci zahlen gar nicht benutzt.
Gruß ledum

anonymous

09:15 Uhr, 25.10.2016

(IV)

F_{n} = \sum_{i = 0}^{n - 1} (\begin{matrix} n - 1 - i \\ i \end{matrix})

und

F_{n - 1} = \sum_{i = 0}^{n - 2} (\begin{matrix} n - 2 - i \\ i \end{matrix})

(IA)

n = 1

F_{1} = \sum_{i = 0}^{0} (\begin{matrix} - i \\ i \end{matrix}) = (\begin{matrix} 0 \\ 0 \end{matrix}) = 1

F_{0} = \sum_{i = 0}^{- 1} (\begin{matrix} - 1 - i \\ i \end{matrix}) = 0

(IS) Nach Definition ist

F_{n + 1} = F_{n} + F_{n - 1}

\sum_{i = 0}^{n} (\begin{matrix} n - i \\ i \end{matrix}) = \sum_{i = 0}^{n - 1} (\begin{matrix} n - 1 - i \\ i \end{matrix}) + \sum_{i = 0}^{n - 2} (\begin{matrix} n - 2 - i \\ i \end{matrix})

Und jetzt?

Werner-Salomon aktiv_icon

11:10 Uhr, 25.10.2016

ich vermute stark, dass Du die Aufgabestellung bereits falsch abgeschrieben hast. In einem Ausdruck

(\binom{n}{k})

kann

k

nie größer als

n

werden.

Vermutlich heißt der zu beweisende Zusammenhang

F_{n + 1} = \sum_{i = 0}^{⌈ \frac{n - 1}{2} ⌉} (\binom{n - i}{i})

dann ist

F_{2} = \sum_{i = 0}^{0} (\binom{1}{0}) = 1

F_{3} = \sum_{i = 0}^{1} (\binom{2 - i}{i}) = (\binom{2}{0}) + (\binom{1}{1}) = 2

anonymous

12:30 Uhr, 25.10.2016

Nein, die Aufgabenstellung ist richtig abgeschrieben.
Der Ausdruck

(\begin{matrix} n \\ k \end{matrix})

mit

k > n

ergibt 0.

ledum aktiv_icon

15:56 Uhr, 25.10.2016

Hallo
dann sieh nach oder frag nach ob die Aufgabenstellung einen Druckfehler enthält, wenn die Summe wirklich bis

n

geht ist die Formel falsch!
Gruß ledum

Werner-Salomon aktiv_icon

21:16 Uhr, 25.10.2016

Hallo HaToMath,

den Induktionsanfang hast Du ja schon gefunden. Also ist

F_{n + 1} = \sum_{i = 0} (\binom{n - i}{i})

für

n = 0

korrekt und die Richtigkeit für

n = 1

und

n = 2

habe ich schon gezeigt (s.o.).
Die obere Grenze für

i

- ob jetzt

⌈ \frac{n - 1}{2} ⌉

oder bis

n

mit der Definition, dass

(\binom{n}{k}) = 0

für

k > n

- lasse ich hier einfach weg. Das spielt letztlich keine Rolle, da alle 'unzulässigen' Glieder =0 sind.

Übergang von

n

nach

n + 1

heißt, einen Ausdruck für

F_{n + 2}

zu finden, der der Rekursionsformel genügt.

n + 1

einsetzen ergibt:

F_{n + 2} = \sum_{i = 0} (\binom{n - i + 1}{i})

Jetzt ausnutzen, dass

(\binom{n}{i}) = (\binom{n - 1}{i}) + (\binom{n - 1}{i - 1})

ist - einsetzen ergibt:

F_{n + 2} = \sum_{i = 0} ((\binom{n - i}{i}) + (\binom{n - i}{i - 1})) = \sum_{i = 0} (\binom{n - i}{i}) + \sum_{i = 0} (\binom{n - i}{i - 1})

die erste Summe ist doch ohne Zweifel

F_{n + 1}

und bei der zweiten substituiere ich

i = k + 1

. Gleichzeitig lasse ich bei der zweiten Summe den ersten Summanden weg, da dieser zu 0 wird. Man erhält:

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

.. und damit wird die zweite Summe zu

F_{n}

- ergo:

F_{n + 2} = F_{n + 1} + F_{n}

Gruß
Werner

anonymous

08:56 Uhr, 26.10.2016

Vielen Dank für deine Ausführungen.

1330432

1330082

	Status: nicht eingeloggt	Noch nicht registriert?