Vektorraum der Fibonacci-Folgen

30.11.2017, 13:26

ForeRunner

Vektorraum der Fibonacci-Folgen

Meine Frage:
Sei $\begin{eqnarray*} Abb( \mathbb{N}, \mathbb{R}) \end{eqnarray*}$ der Vektorraum aller Folgen in $\begin{eqnarray*} \mathbb{R} \end{eqnarray*}$ .
Eine Folge $\begin{eqnarray*} (a_n)_{n\in\mathbb{N}} \end{eqnarray*}$ ist eine Fibonacci-Folge, wenn $\begin{eqnarray*} a_n = a_{n-1} + a_{n-2} \end{eqnarray*}$ für alle $\begin{eqnarray*} n \ge 2 \end{eqnarray*}$ gilt.
Die wohl bekannteste Fibonacci-Folge ist $\begin{eqnarray*} f = (f_n)_{n \in \mathbb{N}}= (0,1,1,2,3,5,8....) \end{eqnarray*}$ .
Wir wollen nun die Menge

$\begin{eqnarray*} Fib := \{(a_n)_{n \in \mathbb{N}} \in Abb(\mathbb{N},\mathbb{R}) : (a_n)_{n \in \mathbb{N}} \end{eqnarray*}$ ist eine Fibonacci-Folge $\begin{eqnarray*} \} \end{eqnarray*}$

aller Fibonacci-Folgen genauer untersuchen.

(a)
Zeigen sie, dass Fib einen Untervektorraum von $\begin{eqnarray*} Abb(\mathbb{N},\mathbb{R}) \end{eqnarray*}$ bildet.

(b)
Bestimmen sie die Dimension von Fib. (Hinweis: Zeigen sie, dass $\begin{eqnarray*} (a_n)_{n \in \mathbb{N}} = (b_n)_{n \in \mathbb{N}} \end{eqnarray*}$ für alle $\begin{eqnarray*} (a_n), (b_n) \in Fib \end{eqnarray*}$ mit $\begin{eqnarray*} a_0=b_0, a_1=b_1 \end{eqnarray*}$ .)

(c)
Zeigen sie, das $\begin{eqnarray*} p1=(\varphi^n) \end{eqnarray*}$ und $\begin{eqnarray*} p2 = ((-\varphi)^{-n}) \end{eqnarray*}$ Fibonacci-Folgen sind eine Basis von Fib bilden. Hier bei ist $\begin{eqnarray*} \varphi= (1+\sqrt{5})/2 \end{eqnarray*}$ der goldene Schnitt ( und $\begin{eqnarray*} -\varphi^{-1}= (1-\sqrt{5})/2 \end{eqnarray*}$ )

(d)
Bestimmen sie die Koordinaten von f bezüglich p1 und p2. Benutzen Sie diese um einen geschlossenen Ausdruck für $\begin{eqnarray*} f_i \end{eqnarray*}$ für alle $\begin{eqnarray*} i \in \mathbb{N} \end{eqnarray*}$ zu finden.

Meine Ideen:
(a)
Wir beginnen damit zu zeigen, dass $\begin{eqnarray*} Fib \subseteq Abb \end{eqnarray*}$ . Das gilt, weil jedes $\begin{eqnarray*} a_n \in Fib \end{eqnarray*}$ darüber definiert ist, dass es in Abb ist, mit der zustzlichen Eigenschaft, dass es eine Fibonacci-Folge ist.
Fib ist nicht leer, da f aus der Aufgabenstellung auf jeden Fall existiert und Element von Fib ist.
Da Fib alle Fibonacci-Folgen enthält, enthält Fib auch ein c, für das gilt $\begin{eqnarray*} a_n+b_n = c_0 \end{eqnarray*}$ und $\begin{eqnarray*} a_{n+1} +b_{n+1} = c_1 \end{eqnarray*}$ für jedes $\begin{eqnarray*} a,b \in Fib \end{eqnarray*}$ und $\begin{eqnarray*} n \in \mathbb{N} \end{eqnarray*}$ . Also ist $\begin{eqnarray*} a+b \in Fib \end{eqnarray*}$ .
Gleiches lässt sich für die Multiplikation mit $\begin{eqnarray*} \alpha \in \mathbb{R} \end{eqnarray*}$ sagen.
$\begin{eqnarray*} \alpha * a_n = c_0 \end{eqnarray*}$ und $\begin{eqnarray*} \alpha * a_n+1 = c_1 \end{eqnarray*}$ . Dieses aus $\begin{eqnarray*} c_1 \end{eqnarray*}$ und $\begin{eqnarray*} c_2 \end{eqnarray*}$ konstruierte c ist wieder eine Fibonacci_Folge und somit wieder in Fib.
Somit haben wir gezeigt, dass Fib ein Untervektorraum von Abb ist.

(b)
Wir zeigen, dass die gleicheit zweier folgen, nur von der Gleicheit der ersten beiden Elemente dieser Folgen abhängt. Also wollen wir für $\begin{eqnarray*} a,b \in Fib \end{eqnarray*}$ zeigen, dass

$\begin{eqnarray*} a_0 = b_0, a_1 = b_1 \Leftrightarrow a = b \end{eqnarray*}$

Also zeigen wir zuerst die Hinrichtung $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ .
Für alle $\begin{eqnarray*} a,b \in Fib \end{eqnarray*}$ gilt mit $\begin{eqnarray*} n \ge 2, n \in \mathbb{N} \end{eqnarray*}$ gilt

$\begin{eqnarray*} a_n = a_{n-1} + a_{n-2} \end{eqnarray*}$ und $\begin{eqnarray*} b_n = b_{n-1} + b_{n-2} \end{eqnarray*}$

Somit ist $\begin{eqnarray*} a_2 = a_1 +a_0 = b_1+b_0 = b_2 \end{eqnarray*}$ mit $\begin{eqnarray*} n = 2 \end{eqnarray*}$ .
Gleiches lässt sich für $\begin{eqnarray*} n=3 \end{eqnarray*}$ sagen, $\begin{eqnarray*} a_3 = a_2 +a_1 = b_2+b_1 = b_3 \end{eqnarray*}$
und so kann für jedes $\begin{eqnarray*} a_n \end{eqnarray*}$ geschlussfolgert werden, dass $\begin{eqnarray*} a_n = b_n \end{eqnarray*}$ wenn
$\begin{eqnarray*} a_0 = b_0, a_1 = b_1 \end{eqnarray*}$ . Somit ist die Hinrichtung gezeigt.

Wir zeigen die Rückrichtung $\begin{eqnarray*} \Leftarrow \end{eqnarray*}$ .

Wenn $\begin{eqnarray*} a = b \end{eqnarray*}$ dann ist auch $\begin{eqnarray*} a_n = b_n \end{eqnarray*}$ und somit müssen auch $\begin{eqnarray*} a_0 = b_0 \end{eqnarray*}$ und $\begin{eqnarray*} a_1 = b_1 \end{eqnarray*}$ sein und wir sind fertig.

Nun haben wir gezeigt, dass die Gleichheit zweier folgen, nur von den ersten zwei Elementen abhängt, also konstruieren diese beiden Elemente die restlichen und sind somit eine Basis von Fib.
Da die Basis aus zwei Elementen abhänig ist, ist Fib zweidimensional.

(c) TODO
(d) TODO

So das sind meine Lösungen zu a und b, an die c und d setzte ich mich wahrscheinlich morgen,
aber ich wollte die fragen trotzdem der vollständigkeithalber schon einmal posten.

Jetzt der Grund warum ich das poste. Und zwar bräuchte ich mal einen Anstoß wie ich an die (c) rangehen soll und vielleicht kann mir jemand sagen, ob ich die a und b so richtig gemacht habe.
Sehr gerne auch Vorschläge wie ich Dinge besser formulieren kann.

Danke schon einmal, dass ihr euch die Zeit nehmt und liebe Grüße.

30.11.2017, 13:54

klarsoweit

Auf diesen Beitrag antworten »

RE: Vektorraum der Fibonacci-Folgen

Zitat:

Original von ForeRunner
(c)
Zeigen sie, das $\begin{eqnarray*} p1=(\varphi^n) \end{eqnarray*}$ und $\begin{eqnarray*} p2 = ((-\varphi)^{-n}) \end{eqnarray*}$ Fibonacci-Folgen sind eine Basis von Fib bilden.

Dieser Satz ist irgendwie verunglückt.

Zitat:

Original von ForeRunner
Da Fib alle Fibonacci-Folgen enthält, enthält Fib auch ein c, für das gilt $\begin{eqnarray*} a_n+b_n = c_0 \end{eqnarray*}$ und $\begin{eqnarray*} a_{n+1} +b_{n+1} = c_1 \end{eqnarray*}$ für jedes $\begin{eqnarray*} a,b \in Fib \end{eqnarray*}$ und $\begin{eqnarray*} n \in \mathbb{N} \end{eqnarray*}$ . Also ist $\begin{eqnarray*} a+b \in Fib \end{eqnarray*}$ .
Gleiches lässt sich für die Multiplikation mit $\begin{eqnarray*} \alpha \in \mathbb{R} \end{eqnarray*}$ sagen.
$\begin{eqnarray*} \alpha * a_n = c_0 \end{eqnarray*}$ und $\begin{eqnarray*} \alpha * a_n+1 = c_1 \end{eqnarray*}$ . Dieses aus $\begin{eqnarray*} c_1 \end{eqnarray*}$ und $\begin{eqnarray*} c_2 \end{eqnarray*}$ konstruierte c ist wieder eine Fibonacci_Folge und somit wieder in Fib.

Was du hier machst verstehe ich nicht. Wieso sollte gelten:
Da Fib alle Fibonacci-Folgen enthält, enthält Fib auch ein c, für das gilt $\begin{eqnarray*} a_n+b_n = c_0 \end{eqnarray*}$ ?

Du mußt doch zeigen, daß für die Folgen (a_n) und (b_n) auch $\begin{eqnarray*} (a_n+b_n) \end{eqnarray*}$ und $\begin{eqnarray*} (\alpha \cdot a_n) \end{eqnarray*}$ Fibonacci-Folgen sind.

30.11.2017, 13:58

Matt Eagle

Auf diesen Beitrag antworten »

Für Teil c.) ist es nützlich zunächst festzustellen, dass

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

denn damit folgt

$\begin{eqnarray*} \varphi^n+\varphi^{n+1}=\varphi^n(1+\varphi)=\varphi^n\cdot\varphi^2=\varphi^{n+2}. \end{eqnarray*}$

30.11.2017, 14:02

Elvis

Auf diesen Beitrag antworten »

Die Hinrichtung bei b) beweist man mit vollständiger Induktion nach n, wobei die Induktionsvoraussetzung für n=0 und n=1 schon erledigt ist.

c) Das kann man für die ersten Folgenglieder leicht nachrechnen, also wird es vermutlich stimmen. Beweis durch vollständige Induktion bietet sich an, da es ja hier um natürliche Zahlen n geht.

d) Der UVR Fib hat die Dimension 2, also muss sich jede Fibonacci-Folge eindeutig als Linearkombination von p1 und p2 darstellen lassen. Es kommt ja nach b) nur auf die ersten beiden Folgenglieder an, also Gleichungen dafür aufstellen : f=a*p1+b*p2 gdw. ...

03.12.2017, 09:40

ForeRunner

Auf diesen Beitrag antworten »

RE: Vektorraum der Fibonacci-Folgen
Erstmal kurz zu (a)

...
Wir zeigen, $\begin{eqnarray*} a + b \in Fib \end{eqnarray*}$

Es gilt, $\begin{eqnarray*} a+b = (a_n)+(b_n) = (a_{n-2}+a_{n-1})+(b_{n-2}+b_{n-1}) = a_{n-2}+a_{n-1}+b_{n-2}+b_{n-1} = (a_{n-2}+a_{n-1}+b_{n-2}+b_{n-1}) = (a_n+b_n) \end{eqnarray*}$

Nun zeigen wir, $\begin{eqnarray*} \alpha * a \in Fib \end{eqnarray*}$ .

Es gilt $\begin{eqnarray*} \alpha * a = \alpha (a_n) = \alpha (a_{n-2}+ a_{n-1}) =\alpha a_{n-2} + \alpha a_{n-1} = (\alpha a_n) \end{eqnarray*}$

Stimmt das und reicht das dann?

Bei c ist dieser Satz tatsächlich wortwörtlich so gegeben.

An die anderen Aufgaben setze ich mich jetzt sofort. Danke für die Tipps auf jeden Fall.

03.12.2017, 10:27

ForeRunner

Auf diesen Beitrag antworten »

RE: Vektorraum der Fibonacci-Folgen
zu (b)

Hier ist mal meine Induktion.

Wir zeigen die Hinrichtung per Induktion mit $\begin{eqnarray*} \sum\limits_{i=2}^{n} a_i = b_i \end{eqnarray*}$
Es gilt $\begin{eqnarray*} a_0 = b_0 \end{eqnarray*}$ und $\begin{eqnarray*} a_1 = b_1 \end{eqnarray*}$ .
Somit folgt für die Induktionsanfang:

$\begin{eqnarray*} \sum\limits_{i=2}^{2} a_i = a_2 = a_0+a_1 = b_0+b_1 = b_2 \end{eqnarray*}$

Induktionsvorraussetzung:
Für jedes n aus N.

Induktionsschritt:

$\begin{eqnarray*} \sum\limits_{i=2}^{n+1} a_i = \sum\limits_{i=2}^{n} a_i + \sum\limits_{i=n+1}^{n+1} a_i \end{eqnarray*}$
Kann ich den folgenden Schritt hier machen?

$\begin{eqnarray*} = \sum\limits_{i=2}^{n} b_i+\sum\limits_{i=n+1}^{n+1} a_i = \sum\limits_{i=2}^{n} b_i + a_{n+1} = \sum\limits_{i=2}^{n} b_i+ a_{n-1} + a_n \end{eqnarray*}$

$\begin{eqnarray*} = \sum\limits_{i=2}^{n} b_i+ b_{n-1} + b_n = \sum\limits_{i=2}^{n} b_i+ b_{n+1} = \sum\limits_{i=2}^{n+1} b_i \end{eqnarray*}$

Somit ist die Hinrichtung gezeigt.

Kann mir jemand sagen ob das stimmt? Besonders der angefragt Schritt?

03.12.2017, 11:38

Elvis

Auf diesen Beitrag antworten »

Da braucht man keine Summen, das geht viel einfacher.

Induktionsanfang: $\begin{eqnarray*} a_0=b_0,a_1=b_1 \end{eqnarray*}$
Induktionsvoraussetzung: $\begin{eqnarray*} \forall k\in\{0,...,n\}:a_k=b_k\Rightarrow a_n=b_n,a_{n-1}=b_{n-1} \end{eqnarray*}$
Induktionsschluß: $\begin{eqnarray*} a_{n+1}=a_n+a_{n-1}=b_n+b_{n-1}=b_{n+1} \end{eqnarray*}$
Also ist $\begin{eqnarray*} \forall n\in \mathbb N_0:a_n=b_n \end{eqnarray*}$

03.12.2017, 17:38

ForeRunner

Auf diesen Beitrag antworten »

RE: Vektorraum der Fibonacci-Folgen
Also für die (c) habe ich das hier raus:

Zunächst stellen wir fest, dass $\begin{eqnarray*} \varphi^2= 1+\varphi \end{eqnarray*}$ sowie $\begin{eqnarray*} -\varphi^{-2} = 1+ (-\varphi^{-1}) \end{eqnarray*}$

Wir zeigen $\begin{eqnarray*} \sum \limits_{i=2}^{n} \varphi^n = \varphi^{n-2} + \varphi^{n-1} \end{eqnarray*}$ für alle n größergleich 2 aus N.

Induktionsanfang:
n = 2

$\begin{eqnarray*} \sum\limits_{i=2}^{2} \varphi^i = \varphi^{2} = 1+ \varphi = \varphi^{2-2}+\varphi^{2-1} \end{eqnarray*}$

Induktionsvorraussetzung:

Wenn $\begin{eqnarray*} \varphi^n = \varphi^{n-2} + \varphi^{n-1} \end{eqnarray*}$ dann auch $\begin{eqnarray*} \varphi^{n+1} = \varphi^{n-1}+ \varphi^{n} \end{eqnarray*}$

induktionsschritt:

$\begin{eqnarray*} \sum\limits_{i=2}^{n+1} \varphi^i = \sum\limits_{i=2}^{n}\varphi^i+\varphi ^{i+1} = \sum\limits_{i=2}^{n}\varphi^i *(1 + \varphi) = \sum\limits_{i=2}^{n}\varphi^i*\varphi ^{2}= \sum\limits_{i=2}^{n}\varphi^{i+2} = \sum\limits_{i=2}^{n}\varphi^{(i+2)-2}+ \varphi ^{(i+2)-1} = \sum\limits_{i=2}^{n}\varphi^i+\varphi ^{i+1} = \sum\limits_{i=2}^{n+1}\varphi^{i-1}+\varphi ^{i} \end{eqnarray*}$

Nun zeigen wir $\begin{eqnarray*} \sum \limits_{i=2}^{n} -\varphi^{-n} = -\varphi^{-(n-2)} + (-\varphi^{-(n-1)}) \end{eqnarray*}$ für alle n größergleich 2 aus N.

Induktionsanfang:
n = 2

$\begin{eqnarray*} \sum\limits_{i=2}^{2} -\varphi^{-i} = -\varphi^{-2} = 1 -\varphi^{-1} = -\varphi^{-(2-2)}+(-\varphi^{-(2-1)}) \end{eqnarray*}$

Induktionsvorraussetzung:

Wenn $\begin{eqnarray*} -\varphi^{-n} = -\varphi^{-(n-2)} + (-\varphi^{-(n-1)}) \end{eqnarray*}$ dann auch $\begin{eqnarray*} -\varphi^{-(n+1)} = -\varphi^{-(n-1)}+(- \varphi^{-n}) \end{eqnarray*}$

induktionsschritt:

$\begin{eqnarray*} \sum\limits_{i=2}^{n+1} -\varphi^{-i} = \sum\limits_{i=2}^{n}-\varphi^{-i}+(-\varphi ^{-(i+1)}) = \sum\limits_{i=2}^{n}-\varphi^{-i} *(1 + (-\varphi^{-1}) = \sum\limits_{i=2}^{n}-\varphi^{-i}*(-\varphi ^{-2})= \sum\limits_{i=2}^{n}-\varphi^{-(i+2)} = \sum\limits_{i=2}^{n}-\varphi^{-((i+2)-2)}+ (-\varphi ^{-((i+2)-1)} = \sum\limits_{i=2}^{n}-\varphi^{-i}+(-\varphi ^{-(i+1)}) = \sum\limits_{i=2}^{n+1}-\varphi^{-(i-1)}+(-\varphi ^{-i}) \end{eqnarray*}$

ich muss leider kurz weg deswegen habe ich den beweis, dass p1 und p2 eine Basis bilden noch nicht. Hier habe ich kurz bewiesen ,dass p1 und p2 überhaupt Fibonaccifolgen sind. Unser Professor mag Induktionen mit Summenzeichen, deswegen habe ich die mal benutzt. Hoffe das ist deswegen nicht falsch.

03.12.2017, 18:01

Elvis

Auf diesen Beitrag antworten »

Die Summenzeichen sind garantiert wieder fehl am Platz. Folgen sind im allgemeinen keine Folgen von Summen. Summenzeichen mag auch dein Professor nur, wenn sie sinnvoll sind, z.B. bei Reihen, das sind Folgen von Partialsummen.

07.12.2017, 11:10

ForeRunner

Auf diesen Beitrag antworten »

Ah alles klar danke! Ich habe das einfach nochmal gemacht, aber diesmal ohne Summenzeichen.
Jetzt macht das für mich auch mehr Sinn.

Danke wie immer für die Hilfe! smile

Neue Frage »

Antworten »

Vektorraum der Fibonacci-Folgen

Verwandte Themen