Vollständige Induktion Fibonacci-Zahlen

Question

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.

Answer 1

Für n=1 ist es klar  F₁ + F₃  =  F₄  wegen 1+2=3

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

Summe i = 0 bis n+1 über F_2i+1  =  F_2(n+1)+2

Also los_: Summe i = 0 bis n+1 über F_2i+1 

=  (  Summe i = 0 bis n über F_2i+1    ) +    F_2(n+1)+1

also mit der Vor_.

=  F_2n+2 +     F_2(n+1)+1

=  F_2n+2 +     F_2n+3

wegen der Def. der Fn also 

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

Comments

Super vielen Dank!

aber wieso gibt:

F2n+2 + F2n+3 = F2n + 4

Aufgrund der Definition der Fn, aber wieso?

Answer 2

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.