Beweis Fibonacci-Zahlen durch vollständige Induktion

26.10.2011, 14:24

fermat106

Beweis Fibonacci-Zahlen durch vollständige Induktion

Meine Frage:
Hallo Leute, folgendes soll ich beweisen, allerdings fehlt mir der Ansatz.

Beweisen Sie:
a) Jede dritte Fibonacci-Zahl ist gerade, die übrigen sind ungerade.
b)
$\begin{eqnarray*} 1 + F1 + F2+....+Fn = Fn+2 \end{eqnarray*}$

Meine Ideen:
Über die vollständige Induktion würde ich erstmal die Induktionsvoraussetzungen beweisen:

Folgende Formeln kenne ich:
$\begin{eqnarray*} F_{1}=F_{2}=1 , F_{n+1}= F_{n}+ F_{n-1} \end{eqnarray*}$
b)
n=1

$\begin{eqnarray*} 1+F_{1} = F_{3} [ F_{3}= F_{2}+F_{1}=2] 2 = 2 \end{eqnarray*}$

Wie gehe ich beim Induktionsschritt vor?? Bei der Teilaufgabe a habe ich überhaupt keinen Ansatz....evtl über Modulo, aber ich wüßte nicht wie.

26.10.2011, 14:45

René Gruber

Auf diesen Beitrag antworten »

Du musst einfach die eigentliche Behauptung anpassen, die du per Vollständiger Induktion beweisen willst. Passend wäre da z.B.

Zitat:

A(n): $\begin{eqnarray*} F_{3n} \equiv 0\bmod 2, \; F_{3n+1} \equiv 1\bmod 2, \; F_{3n+2} \equiv 1\bmod 2 \end{eqnarray*}$

Induktionsanfang $\begin{eqnarray*} n=0 \end{eqnarray*}$ sollte klar sein.

Induktionsschluss $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ : Hier wird dreimal $\begin{eqnarray*} F_k = F_{k-1}+F_{k-2} \end{eqnarray*}$ genutzt, und zwar für $\begin{eqnarray*} k=3n+3,3n+4,3n+5 \end{eqnarray*}$ , wobei die Induktionsvoraussetzung einfließt.

26.10.2011, 19:59

fermat106

Auf diesen Beitrag antworten »

Hallo René, erstmal vielen Dank. Komme aber trotzdem nicht weiter. Ich habe überhaupt keine Ahnung.

Die Induktionsverankerung ist mir auch nicht klar. Wäre um Unterstützung dankbar!

26.10.2011, 21:03

fermat106

Auf diesen Beitrag antworten »

So habe ich an die b) herangewagt:

Induktionsschritt:

$\begin{eqnarray*} 1+\sum\limits_{k=1}^{n+1} F_{k} = F_{n+3} = 1+\sum\limits_{k=1}^{n} F_{k} + F_{n+1} = 1 + F_{n+2} + F_{n+1} = F_{n+3} \end{eqnarray*}$

Jetzt habe ich eine ähnliche Aufgabe entdeckt, wo ich nicht genau wüßte wie ich das machen würde:
Wie wäre die Induktionsverankerung und der Induktionsschritt bei folgender Aufgabe:

$\begin{eqnarray*} 1+F_{2}+F{4}+......+F_{2n-2} + F_{2n} = F_{2n+1} \end{eqnarray*}$
Was wähle ich bei der Induktionsverankerung für n?

Beim Induktionsschluss binn ich folgendermaßen vorgegangen:
$\begin{eqnarray*} 1+\sum\limits_{k=1}^{n+1} F_{2n} = F_{2n+3} = 1+\sum\limits_{k=1}^{n} F_{2n} + F_{2n+1} = 1 + F_{2n+1} + F_{2n+1} = \end{eqnarray*}$

Ich komme aber nicht auf die F_{2n+3}

Neue Frage »

Antworten »

Beweis Fibonacci-Zahlen durch vollständige Induktion

Verwandte Themen