Vollständige Induktion

28.10.2023, 15:15

Evelyn2003

Vollständige Induktion

Ich soll mittels der vollständigen Induktion beweisen das die Identität

$\begin{eqnarray*} \sum\limits_{k=0}^{n} f^{2}_k = f_n \cdot f_{n+1} \end{eqnarray*}$

für die Fibonacci-Zahlenfolge $\begin{eqnarray*} (f_k)_{k \in \mathbb N_0} \end{eqnarray*}$ mit $\begin{eqnarray*} f_0 := 0 \end{eqnarray*}$ und $\begin{eqnarray*} f_1 := 1 \end{eqnarray*}$ und Rekursionsvorschrift $\begin{eqnarray*} f_n :=f_{n-2} + f_{n+1} \end{eqnarray*}$ gilt.

Induktionsverankerung $\begin{eqnarray*} A(1) \end{eqnarray*}$
$\begin{eqnarray*} \sum\limits_{k=0}^{n} f^{2}_0 = f_1 \cdot f_{1+1} \end{eqnarray*}$
$\begin{eqnarray*} \sum\limits_{k=0}^{n} f^{2}_0 = f_1 \cdot f_{2} \end{eqnarray*}$

$\begin{eqnarray*} f_{2} = f_{2-2} + f_{2-1} = f_{0} + f_{1} = 0 + 1 = 1 \end{eqnarray*}$

$\begin{eqnarray*} 1^2 = 1 \cdot 1 \end{eqnarray*}$
$\begin{eqnarray*} 1 = 1 \end{eqnarray*}$

Induktionsschritt $\begin{eqnarray*} A(n+1) \end{eqnarray*}$
$\begin{eqnarray*} \sum\limits_{k=0}^{n} f^{2}_k = f_{n+1} \cdot f_{(n+1)+1} = \sum\limits_{k=0}^{n} f^{2}_k = f_{n+1} \cdot f_{n+2} \end{eqnarray*}$

$\begin{eqnarray*} f_{n+1} =f_{(n+1)-2} + f_{(n+1)+1} = f_{n-1} + f_{n+2} \end{eqnarray*}$

einsetzen?
$\begin{eqnarray*} \sum\limits_{k=0}^{n} f^{2}_k = (f_{n-1} + f_{n+2}) \cdot f_{n+2} \end{eqnarray*}$

$\begin{eqnarray*} f_{n+2} =f_{n+1} - f_{n-1} \end{eqnarray*}$

$\begin{eqnarray*} \sum\limits_{k=0}^{n} f^{2}_k = (f_{n-1} + f_{n+2}) \cdot (f_{n+1} - f_{n-1}) \end{eqnarray*}$

Wie geht es hier bitte weiter? verwirrt

IV ?

$\begin{eqnarray*} f_n \cdot f_{n+1} = (f_{n-1} + f_{n+2}) \cdot (f_{n+1} - f_{n-1}) \end{eqnarray*}$

28.10.2023, 15:27

nichteuerernst

Auf diesen Beitrag antworten »

RE: vollständige Induktion 2
Hast du eventuell in der Rekursionsvorschrift einen Vorzeichenfehler? $\begin{eqnarray*} f_{n-1}+f_{n+2} \end{eqnarray*}$ ist seltsam.

28.10.2023, 15:30

Evelyn2003

Auf diesen Beitrag antworten »

RE: vollständige Induktion 2

Zitat:

Original von nichteuerernst
Hast du eventuell in der Rekursionsvorschrift einen Vorzeichenfehler? $\begin{eqnarray*} f_{n-1}+f_{n+2} \end{eqnarray*}$ ist seltsam.

Auf meinen Aufgabenblatt steht: $\begin{eqnarray*} f_n :=f_{n-2} + f_{n-1} \end{eqnarray*}$ Hab zwei Mal nachgeschaut.

28.10.2023, 19:33

Mathema

Auf diesen Beitrag antworten »

Im Induktionsschritt ist $\begin{eqnarray*} \sum\limits_{k=0}^{n\color{red}{+1}} f^{2}_k = f_{n+1} \cdot f_{(n+1)+1} \end{eqnarray*}$ zu zeigen. Nun ist:

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} f^{2}_k = \sum\limits_{k=0}^{n} f^{2}_k+f_{n+1}^2 =\ldots= f_{n+1} \cdot f_{n+2} \end{eqnarray*}$

28.10.2023, 22:07

Evelyn2003

Auf diesen Beitrag antworten »

Zitat:

Original von Mathema
Im Induktionsschritt ist $\begin{eqnarray*} \sum\limits_{k=0}^{n\color{red}{+1}} f^{2}_k = f_{n+1} \cdot f_{(n+1)+1} \end{eqnarray*}$ zu zeigen. Nun ist:

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} f^{2}_k = \sum\limits_{k=0}^{n} f^{2}_k+f_{n+1}^2 =\ldots= f_{n+1} \cdot f_{n+2} \end{eqnarray*}$

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} f^{2}_k = \sum\limits_{k=0}^{n} f^{2}_k+f_{n+1}^2 \stackrel{IV}{=} (f_n \cdot f_{n+1}) + f^2_{n+1}=\ldots= f_{n+1} \cdot f_{n+2} \end{eqnarray*}$

$\begin{eqnarray*} f^2_{n+1} = f_{n+1} \cdot f_{n+1} \end{eqnarray*}$
$\begin{eqnarray*} f_{n+1} = f_{(n+1)-2} + f_{(n+1)-1} = f_{n-1} + f_{n} \end{eqnarray*}$

$\begin{eqnarray*} f^2_{n+1} = f_{n+1} \cdot f_{n+1} = (f_{n-1} + f_{n}) \cdot (f_{n-1} + f_{n}) = f^2_{n-1} +2 \cdot f_{n-1} \cdot f_n + f^2_n \end{eqnarray*}$

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} f^{2}_k = \sum\limits_{k=0}^{n} f^{2}_k+f_{n+1}^2 \stackrel{IV}{=} (f_n \cdot f_{n+1}) + f^2_{n+1}=(f_n \cdot f_{n+1}) + (f^2_{n-1} +2 \cdot f_{n-1} \cdot f_n + f^2_n) = \ldots= f_{n+1} \cdot f_{n+2} \end{eqnarray*}$

$\begin{eqnarray*} f^2_n = f_n \cdot f_n \end{eqnarray*}$
$\begin{eqnarray*} f_n = f_{n-2} +f_{n-1} \end{eqnarray*}$
$\begin{eqnarray*} f^2_n = f_n \cdot f_n = (f_{n-2} +f_{n-1}) \cdot (f_{n-2} +f_{n-1}) = f^2_{n-2} + 2 \cdot f_{n-2} \cdot f_{n-1} + f^2_{n-1} \end{eqnarray*}$

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} f^{2}_k = \sum\limits_{k=0}^{n} f^{2}_k+f_{n+1}^2 \stackrel{IV}{=} (f_n \cdot f_{n+1}) + f^2_{n+1}=(f_n \cdot f_{n+1}) + (f^2_{n-1} +2 \cdot f_{n-1} \cdot f_n + f^2_n) = (f_n \cdot f_{n+1}) + (f^2_{n-1} +2 \cdot f_{n-1} \cdot f_n + (f^2_{n-2} + 2 \cdot f_{n-2} \cdot f_{n-1} + f^2_{n-1} )) =\ldots= f_{n+1} \cdot f_{n+2} \end{eqnarray*}$

Vielen Dank, Mathema! smile

komme aber trotz deines großartigen Hinweises nicht mehr weiter unglücklich

29.10.2023, 06:32

Mathema

Auf diesen Beitrag antworten »

Du denkst irgendwie viel zu kompliziert. Du musst doch nur einmal ausklammern und bist dann fertig.

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} f^{2}_k = \sum\limits_{k=0}^{n} f^{2}_k+f_{n+1}^2 \stackrel{IV}{=} (f_n \cdot f_{n+1}) + f^2_{n+1}=f_{n+1}\left(f_n+f_{n+1}\right)= f_{n+1} \cdot f_{n+2}\quad \blacksquare \end{eqnarray*}$

Schönen Sonntag! smile

29.10.2023, 10:08

Evelyn2003

Auf diesen Beitrag antworten »

Zitat:

Original von Mathema
Du denkst irgendwie viel zu kompliziert. Du musst doch nur einmal ausklammern und bist dann fertig.

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} f^{2}_k = \sum\limits_{k=0}^{n} f^{2}_k+f_{n+1}^2 \stackrel{IV}{=} (f_n \cdot f_{n+1}) + f^2_{n+1}=f_{n+1}\left(f_n+f_{n+1}\right)= f_{n+1} \cdot f_{n+2}\quad \blacksquare \end{eqnarray*}$

Schönen Sonntag! smile

Wieso sind bitte die beiden Terme gleich? gelten bei Indizes die Gesetze analog wie bei Potenzgesetze?

$\begin{eqnarray*} f_{n+1}\left(f_n+f_{n+1}\right)= f_{n+1} \cdot f_{n+2} \end{eqnarray*}$

Vielen Dank, Mathema! Dir wünsche ich ebenfalls einen schönen Sonntag. smile

29.10.2023, 10:22

Mathema

Auf diesen Beitrag antworten »

RE: vollständige Induktion 2
Das ist doch die Definition der Fibonacci-Zahlen.

Zitat:

Original von Evelyn2003
Auf meinen Aufgabenblatt steht: $\begin{eqnarray*} f_n :=f_{n-2} + f_{n-1} \end{eqnarray*}$ Hab zwei Mal nachgeschaut.

Hier dann eben mit $\begin{eqnarray*} n\mapsto n+2 \end{eqnarray*}$ :

$\begin{eqnarray*} f_{n+2} =f_{n+2-2} + f_{n+2-1}=f_n+f_{n+1} \end{eqnarray*}$

29.10.2023, 10:27

Evelyn2003

Auf diesen Beitrag antworten »

RE: vollständige Induktion 2

Zitat:

Original von Mathema
Das ist doch die Definition der Fibonacci-Zahlen.

Zitat:

Original von Evelyn2003
Auf meinen Aufgabenblatt steht: $\begin{eqnarray*} f_n :=f_{n-2} + f_{n-1} \end{eqnarray*}$ Hab zwei Mal nachgeschaut.

Hier dann eben mit $\begin{eqnarray*} n\mapsto n+2 \end{eqnarray*}$ :

$\begin{eqnarray*} f_{n+2} =f_{n+2-2} + f_{n+2-1}=f_n+f_{n+1} \end{eqnarray*}$

Vielen Dank. Da wäre ich leider selber nicht darauf gekommen. Wink

Neue Frage »

Antworten »

Vollständige Induktion

Verwandte Themen