Fibonacci-Zahlen

26.11.2006, 22:01

Matheass

Fibonacci-Zahlen

Hallo,

und zwar heisst die Aufgabe: Beweisen sie die Identität:

http://www.oertelserv.de/002/Unbenannt.JPG

Die zahlen sind so definiert:

F0=F1=1

Fn=Fn-1 + Fn-2 für n>1

Wenn man bespiele für n wählt sieht man das sofort, aber wie soll man das Beweisen?? Hat jemand ne idee??

26.11.2006, 22:03

Dual Space

Auf diesen Beitrag antworten »

RE: Fibonacci-Zahlen
Hast du es schon mal über vollständige Induktion versucht?

26.11.2006, 22:08

Matheass

Auf diesen Beitrag antworten »

Nee, weil man doch damit nur zeigen kann das eine seite gilt, aber damit kann man doch nicht das gleicheitszeichen beweisen oder? Man muss irgendwie durch umformen der einen seite auf die andere kommen, oder bin ich auf dem holzweg?

26.11.2006, 22:33

Dual Space

Auf diesen Beitrag antworten »

Zitat:

Original von Matheass
Nee, weil man doch damit nur zeigen kann das eine seite gilt, aber damit kann man doch nicht das gleicheitszeichen beweisen oder?

Das ist Unfug. Natürlich kann man die Gleicheit mittels Induktion beweisen. Versuch dich und fang einfach mal an.

Induktionsanfang: n=1 ...

26.11.2006, 22:35

Auf diesen Beitrag antworten »

doch:
Induktionschritt :

Summe(0,m+1) F_i = Summe(0,m) F_i + F_(m+1) = F_(m+2) - 1 + F_(m+1) = F_(m+3)-1

wenn du einen induktionsanfang machst und jedes gleichheitszeichen hier nicht mit einem fragezeichen beantwortest, dürfte die aufgabe fertig sein...

26.11.2006, 22:46

Matheass

Auf diesen Beitrag antworten »

Naja, das Problem ist nur das diese Übung noch nicht zur "Vollständigen Induktion" gehört...quasi hatten wir das noch garnicht...also geht das irgendwie anders?

27.11.2006, 08:34

Dual Space

Auf diesen Beitrag antworten »

Naja man kann es auch durch "induktives hinschreiben" machen, obwohl ich das nicht als Beweis anerkennen würde (zumindest würde ich dir wahrscheinlich nicht die volle Punktzahl geben). Damit meine ich:

(1) schreib $\begin{eqnarray*} F_{n+2} \end{eqnarray*}$ auf der rechten Seite als $\begin{eqnarray*} F_{n+1}+F_n \end{eqnarray*}$ und subtrahiere die Gleichung mit $\begin{eqnarray*} F_n \end{eqnarray*}$ .

(2) schreib $\begin{eqnarray*} F_{n+1} \end{eqnarray*}$ auf der rechten Seite als $\begin{eqnarray*} F_{n}+F_{n-1} \end{eqnarray*}$ und subtrahiere die Gleichung mit $\begin{eqnarray*} F_{n-1} \end{eqnarray*}$ .

.
.
.

(n) schreib $\begin{eqnarray*} F_{2} \end{eqnarray*}$ auf der rechten Seite als $\begin{eqnarray*} F_{1}+F_0 \end{eqnarray*}$ und subtrahiere die Gleichung mit $\begin{eqnarray*} F_0 \end{eqnarray*}$ .

Dann steht noch da: $\begin{eqnarray*} 0=F_1-1 \end{eqnarray*}$ .

29.11.2006, 20:38

Matheass

Auf diesen Beitrag antworten »

Ok das hat geklappt...

Jetzt hab ich aber noch so eine komische aufgabe auch mit den fibunacci zahlen...

und zwar soll man beweisen, das F(3*n) und F(3*n+1) ungerade und F(3*n+2) gerade ist

Wie macht man denn sowas??

29.11.2006, 20:39

Dual Space

Auf diesen Beitrag antworten »

Tja ... also hier wirst du wohl um eine Induktion nicht drumherum kommen. Augenzwinkern

29.11.2006, 20:41

Matheass

Auf diesen Beitrag antworten »

ja hab ich versucht ich komm auf ein wiederspruch, als es gilt nicht für n+1 hmmmm

29.11.2006, 20:52

Dual Space

Auf diesen Beitrag antworten »

Tjoa ... da hast du Recht, denn F(3)=2 ist augenscheinlich NICHT ungerade. Also überprüf nochmal deine Aufgabe.

29.11.2006, 21:05

leo001

Auf diesen Beitrag antworten »

öööhm doch, denn es ist definiert: F(0) = F(1)=1 und F(n)=F(n-1)+F(n-2)

also F(3)= F(2)+F(1) = F(1)+F(0) + 1 = 1 + 1+1=3 -> ungerade....

ich hab das mit der induktion so gemacht:

InduktionsAnfang: F(3n) und F(3n+1) ist ungerade und F(3n+2) gerade

gilt für n=0:

F(3*0)=F(0)=1 ->ungerade
F(3*0+1) = F(1)=1 -> ungerade

F(3*0+2) = F(1) + F(0) = 1+1 = 2 ->gerade

Stimmt also alles..

jetzt fürn n+1:

F(3(n+1))= F(3n+3) = F(3n+1) + F(2)
--> F(3n+1) ist ungerade laut I.A.
und F(2) ist gerade --> ungerade+gerade ist immer ungerade--stimmt

F(3(n+1)+1)=F(3n+4) = F(3n+2) + F(2)
--> F(3n+2) ist gerade laut I.A.
und F(2) auch---gerade + gerade immer =gerade ---stimmt also nicht

Wiederspruch??

Oder was mach ich falsch

29.11.2006, 21:16

piloan

Auf diesen Beitrag antworten »

falsch falsch ..was ich geschrieben habe ... Augenzwinkern

29.11.2006, 21:46

Matheass

Auf diesen Beitrag antworten »

hööö?

29.11.2006, 21:48

Dual Space

Auf diesen Beitrag antworten »

leo001: Stimmt. Hatte $\begin{eqnarray*} F_0=0 \end{eqnarray*}$ im Hinterkopf. Augenzwinkern