Beweise an der Fibonacci-Folge

20.10.2010, 23:16	terri	Auf diesen Beitrag antworten »
Beweise an der Fibonacci-Folge Hi, ich habe hier 2 Beweise an der wohl bekannten Fibonaccifolge zu führen, allerdings sehe ich kaum eine Chance, selbst drauf zu kommen. Die Beweise sollen mit voll. Induktion geführt werden. Also 1: für alle n aus N gilt $\begin{eqnarray} F(n) \leq 2^{n} \end{eqnarray}$ Naja der Induktionsanfang ist hier ja einfach: F(0) := 0; $\begin{eqnarray} 2^{0} \end{eqnarray}$ := 1, somit 0<1 also F(0)< $\begin{eqnarray} 2^{0} \end{eqnarray}$ ; Hier weiß ich beim Induktionsschritt nicht mehr weiter; ich hab jetzt zwar mal ungeformt bis ich (F(n+1)=F(n+2) - F(n)) <= 22^n hatte, allerdings sehe ich da immer noch nicht die Erkenntnis drin. Auf Wikipedia gibts zwar ein Haufen Sätze zu den Fibonacci-Zahlen, aber die müsste vorher ja auch beweisen, was nicht grade einfacher sein dürfte. 2. Aufgabe Für alle n aus N mit $\begin{eqnarray} n \geq 11 gilt: 2^{n} * F(n) \geq 3^{n} \end{eqnarray*}$ hmm ... soll ich hier im Induktionsanfang einfach n=11 einsetzen und die konkreten Werte ausrechnen? Wäre ja nicht das Problem. Den Induktionsschritt kann ich mir hier allerdings garnicht vorstellen, vermutlich muss man eine Erkenntnis benutzen, die man unter 1.) gewonnen hat. Diese rekursive vorschrift blockiert irgendwie mein Denken, aber mit der expliciten Form werde ich wohl auch nicht weiter kommen - besonders da ich die ja auch herleiten müsste, einfach behaupten die würde gelten geht ja wohl nicht. Wäre dankbar für Hilfe mfg terri PS: Ich habe grade gesehen dass ich hier in die Schulmathematik gepostet habe. Hoffe das ist nicht schlimm .
21.10.2010, 11:46	tmo	Auf diesen Beitrag antworten »
Ich habe mal in die Hochschulmathematik verschoben. Wichtig ist beim Induktionsschritt, dass du sowohl die Aussage für n nutzt, als auch die Aussage für n-1. D.h. du setzt voraus: $\begin{eqnarray} F(n) \leq 2^n \end{eqnarray}$ und $\begin{eqnarray} F(n-1) \leq 2^{n-1} \end{eqnarray}$ und folgerst: $\begin{eqnarray} F(n+1) \leq 2^{n+1} \end{eqnarray}$ . Um das machen zu können, musst du allerdings auch zwei Induktionsanfänge zeigen, d.h. n=0 und n=1. Die 1. Aufgabe könnte man auch noch "nur mit n -> n+1" lösen, allerdings wird man spätestens bei der 2. Aufgabe mehr brauchen, weshalb ich es direkt schon für die 1. Aufgabe vorschlage.
22.10.2010, 08:52	physi freak	Auf diesen Beitrag antworten »
aw Hmm das hilft mir aber nicht weiter mit b), meinst du, dass wenn ich meine Induktionsanfänge n=12 und n-1=11 verwende, also nach dem Schritt (F(n+1)) --> F(n)+F(n-1) sage, dass, das ja meine Induktionsanfänge waren und wenn eins von beidem größer ist dann auch beide addiert??? LG physi
22.10.2010, 09:56	Manni Feinbein	Auf diesen Beitrag antworten »
RE: aw Im Induktionsschritt möchtest Du aus $\begin{eqnarray} F_n\geq\left(\frac 32\right)^n\text{ und }F_{n+1}\geq\left(\frac 32\right)^{n+1} \end{eqnarray}$ folgern, daß $\begin{eqnarray} F_{n+2}\geq\left(\frac 32\right)^{n+2} \end{eqnarray}$ was mit der Rekursionsformel für die Fibonaccizahlen nicht schwer fallen sollte. Also brauchst Du auch zwei aufeinanderfolgende Werte (hier eben 11 und 12), um die Induktion zu verankern.
23.10.2010, 09:41	physi_freak	Auf diesen Beitrag antworten »
hey danke super sache
23.10.2010, 13:49	PHY Hannes	Auf diesen Beitrag antworten »
kann mich dem nur anschließen, vielen Dank!
Anzeige

24.10.2010, 14:01	nicht registriert	Auf diesen Beitrag antworten »
RE: aw Kann ich denn einfach so zwei Gleichungen in der Induktionsvoraussetzung annehmen? Das würde doch dem ganzen Prinzip der Induktion widersprechen. Denn wenn eine Annahme für n-1 und n gilt sowie für ein erstes Element (z.B. Null), dann gilt sie für alle beliebigen n. Denn wir haben angenommen, dass n der Nachfolger von n-1 ist (so wie normalerweise beim Induktionsbeweis k+1 der Nachfolger von k ist). Wir hätten also mit Induktionsbehauptung und -anfang schon festgelegt, dass die Gleichung für alle n gilt. Angenommen ich dürfte das. Ich hätte in Aufgabe 2: F(n+2)= F(n+1) + F(n)>=1,5^(n+2) Was kann ich daraus schließen? In der ersten Aufgabe ging das ja noch. Aber hier komme ich nicht weiter.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »