+1 Daumen
5,1k Aufrufe

Aufgabe (Fibonacci):

Die Fibonacci Folge ist für alle \( n \in \mathbb{N} \) definiert durch:
$$ F_{0}=0, F_{1}=1, F_{n+2}=F_{n+1}+F_{n} $$

a) Zeigen Sie mit Hilfe vollständiger Induktion, dass für alle \( n \in \mathbb{N} \) gilt:
$$ \sum \limits_{i=0}^{n} F_{2 i+1}=F_{2 n+2} $$


Wir haben in der Schule das Thema Induktion. Die grundlegende Vorgangsweise der vollständigen Induktion verstehe ich. Nun sollen wir aber die Fibonacci - Folge anhand der vollständigen Induktion beweisen, was ich etwas schwierig finde. Ich wäre sehr froh, wenn mir jemand einen Tipp geben könnte.

von

2 Antworten

+1 Daumen

Für n=1 ist es klar  F1 + F3  =  F4  wegen 1+2=3

Angenommen, es gilt für ein n dann ist zu zeigen.

Summe i = 0 bis n+1 über F2i+1  =  F2(n+1)+2

Also losSumme i = 0 bis n+1 über F2i+1 

=  (  Summe i = 0 bis n über F2i+1    ) +    F2(n+1)+1

also mit der Vor.

=  F2n+2 +     F2(n+1)+1

=  F2n+2 +     F2n+3

wegen der Def. der Fn also 

= F 2n+4    =  F2(n+1)+2     q.e.d. 

von 228 k 🚀

Super vielen Dank!

aber wieso gibt:

F2n+2 + F2n+3 = F2n + 4

Aufgrund der Definition der Fn, aber wieso?

+1 Daumen
Nun sollen wir aber die Fibonacci - Folge anhand der vollständigen Induktion beweisen.

Du sollst nicht die Fibonacci-Folge beweisen sondern eine Aussage über die Fibonacci-Folge. Das ist ein Unterschied.

Das könnte wie folgt aussehen:

Induktionsanfang \( n=0 \)

\( \sum \limits_{\mathrm{k}=0} ^{\mathrm{n}} \mathrm{F}_{2 \mathrm{k}+1}=\mathrm{F}_{2 \mathrm{n}+2} \)

\( \mathrm{F}_{2·0+1}=\mathrm{F}_{2·0+2} \)
\( \mathrm{F}_{1}=\mathrm{F}_{2} \)
stimmt, wie sich leicht feststellen lässt

Induktionsschritt \( n \rightarrow n+1 \)

\( \sum(\mathrm{k}=0 \text { bis } \mathrm{n}+1) \mathrm{F}_{2 \mathrm{k}+1}=\mathrm{F}_{2(\mathrm{n}+1)+2} \)
\( \Sigma(\mathrm{k}=0 \text { bis } \mathrm{n}) \mathrm{F}_{2 \mathrm{k}+1}+\mathrm{F}_{2(\mathrm{n}+1)+1}=\mathrm{F}_{2(\mathrm{n}+1)+2} \)
\( \mathrm{F}_{2 \mathrm{n}+2}+\mathrm{F}_{2 \mathrm{n}+3}=\mathrm{F}_{2 \mathrm{n}+4} \)

stimmt nach der Definition der Fibonacci Zahlen. 

von 388 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community