+1 Daumen
2k Aufrufe

Ich hänge bei der Aufgabe fest, könnte mir jemand dabei helfen ?

Seien \( F_{n} \) die Fibonacci-Zahlen. Beweisen Sie mit vollständiger Induktion:
(a) Für alle \( n \in \mathbb{N} \) gilt: \( \sum \limits_{i=1}^{n} F_{i}^{2}=F_{n} F_{n+1} \).
(b) Für alle \( n \in \mathbb{N}, n \geq 2 \) gilt: \( F_{n+1} F_{n-1}-F_{n}^{2}=(-1)^{n} \).
(c) Für alle \( n \in \mathbb{N} \) gibt es \( k \in \mathbb{N} \) und \( c_{1}, \ldots, c_{k} \in \mathbb{N}_{\geq 2} \), so dass \( c_{i+1}>c_{i}+1 \) für \( i \in\{1, \ldots, k-1\} \) und

n =  \( \sum \limits_{i=1}^{k} F_{c_{i}} \)

Avatar von

Wo hängst du genau fest? Schon beim Induktionsanfang? Den solltest du doch noch alleine hinbekommen oder auch nicht?

2 Antworten

0 Daumen
 
Beste Antwort

Hallo,

(c) Für alle \( n \in \mathbb{N} \) gibt es \( k \in \mathbb{N} \) und \( c_{1}, \ldots, c_{k} \in \mathbb{N}_{\geq 2} \), so dass \( c_{i+1}>c_{i}+1 \) für \( i \in\{1, \ldots, k-1\} \) und \(n=\sum \limits_{i=1}^{k} F_{c_{i}} \)

Alle Zahlen \(n\), die selbst Fibonaccizahlen sind lassen sich so darstellen, wobei die Summe dann eben nur aus dem einem Summanden besteht. Man muss obiges also nur für Zahlen zeigen, die zwischen den Fibonaccizahlen liegen.

Als Induktionsanfang betrachte ich nun alle(!) Zahlen, die zwischen \(F_4=3\) und \(F_5=5\) liegen. Das ist nur die Zahl \(n=4\). $$4 = 1+3=F_2 + F_4 =\sum\limits_{i=1}^2 F_{c_i} \quad c_i\in\{2,\,4\} \quad c_2 \gt c_1 + 1$$Der Induktionsanfang gilt also für die Zahl \(n=4\) im Intervall \(n \in\, ]F_4,\,F_5[ \) bzw. allgemein im Intervall \(n \in\,]F_{c_k},\,F_{c_{k+1}}[\) mit \(c_k=4\).

Im Induktionsschritt zeigt man nun, dass dies auch für \(c_{k+1}\) gilt

und damit für alle Zahlen \(n\) im Intervall \(n \in\,]F_{c_{k+1}},\,F_{c_{k+2}}[\)

$$\begin{aligned}n &= F_m + n' &&|\,F_m \lt n \lt F_{m+1}=F_m+F_{m-1} \\ \implies n' &\lt F_{m-1} \\ n' &= \sum\limits_{i=1}^{k} F_{c_i} &&|\, \text{lt. Vor.:}\space c_k \lt m-1 \\\implies n &= F_m + \sum\limits_{i=1}^{k} F_{c_i} &&|\, m \gt c_k + 1 \\ n &= \sum\limits_{i=1}^{k+1} F_{c_i}&&\text{mit}\space c_{k+1} \gt c_k + 1\\&\text{q.e.d.}\end{aligned}$$


(b) Für alle \( n \in \mathbb{N}, n \geq 2 \) gilt: \( F_{n+1} F_{n-1}-F_{n}^{2}=(-1)^{n} \).

Induktionsanfang mit \(n=2\): $$F_3F_1 - F_2^2 = 2\cdot 1 - 1^2 = 1 = (-1)^2\space \checkmark$$Und der Induktionsschritt:$$\begin{aligned}F_{n+2}F_{n} - F_{n+1}^2 &= (F_{n+1}+F_n)F_n - F_{n+1}(F_n+F_{n-1})\\ &= F_{n+1}F_n + F_n^2 - F_{n+1}F_n - F_{n+1}F_{n-1}\\ &=  F_n^2 - F_{n+1}F_{n-1}\\ &=  (\underbrace{F_{n+1}F_{n-1} - F_n^2}_{=(-1)^n})\cdot(-1)\\ &= (-1)^{n+1}\\&\text{q.e.d.} \end{aligned}$$


(a) Für alle \( n \in \mathbb{N} \) gilt: \( \sum \limits_{i=1}^{n} F_{i}^{2}=F_{n} F_{n+1} \).

siehe Antwort von mathef bzw. hier.

Gruß Werner

Avatar von 48 k

Teil (b) vervollständigt.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community