Fibonacci Zahlen zu zeigen.

Question

Hi,

Die Fibonacci-Zahlen sind ja so definiert:

a₀=1, a₁=1, a_n=a_n-2+a_n-1, n ≥ 1

Nun habe ich zu zeigen, dass "n ≤ a_n ≤ 2n"

Mit Induktion:

n=1  1 ≤ 1 ≤ 2 ✓

n→n+1 (n+1) ≤ a_n+1 ≤ 2ⁿ⁺¹ ⇒  (n+1) ≤ a_n-1 +a_n ≤ 2* 2ⁿ

Ich kann nun einfach sagen, dass aus der Anfangsbedingung folgt:

1 ≤ a_n-1 ≤ 2

Was mir das aber schlussendlich bringt ist mir nicht so klar. (Ausser natürlich, dass ich 1<2 bewiesen habe)

Danke und einen guten Tag

Answer 1

die Stelle \( 1 \leq a_{n-1} \leq 2 \) kommt mir direkt ein bisschen falsch vor.

Der Induktionsschritt ist ebenso falsch. Dieser beginnt mit dem, was beim Induktionsschritt im Rahmen des Beweisprinzipes "vollständige Induktion" gezeigt werden soll: Du solltest für die Aussage H(n) zeigen, dass H(n+1) folgt.

Zeigst du, dass aus H(n+1) die Aussage H(n) folgt, so könntest du höchstens mit einem endlichen Induktionsanfang H(N) zeigen, dass die Aussage für alle \( n \leq N \) gilt, dieses Prinzip wäre gewissermaßen eine "unvollständige Induktion".

MfG

Mister

Comments

Hallo Mister

Danke für deine Hilfe

Hast du mir ein Schlagwort oder ein Tip mit welchem ich mich für einen Beweis orientieren könnte?

Lg

---

ja. dein Induktionsanfang muss n = 1 und n = 2 umfassen. Dein Induktionsschritt muss die Aussagen für \( a_n \) und \( a_{n+1} \) zu einer wahren Aussage für \( a_{n+2} \) zusammenführen. Du beweist dann, dass aus H(n) und H(n+1) die Aussage H(n+2) folgt:

\( H(n), H(n+1) \Rightarrow H(n+2) \).

MfG

Mister

---

Hallo Mister

Ich habe mir nun ein paar Überlegungen dazu gemacht.

a_n = a_n-2 + a_n-1

n = 0  => a_0:=1

n = 1  => a_1:=1

n -> n+1  a_n+1 = a_n-1 + a_n  = a_n-1 + a_n-2 + a_n-1

Jetzt muss ich ja nun beweisen das dies wiederum = a_n+1.

Und da weiss ich nicht weiter.

---

Diese Aussage steht doch aber schon da. Du musst die Aussage

\( 1 \leq a_{n+1} \leq 2^{n+1} \)

beweisen mit Hilfe der beiden Induktionsvoraussezungen \( 1 \leq a_{n-1} \leq 2^{n-1} \) und \( 1 \leq a_{n} \leq 2^{n} \). (Da dies zwei Induktionsvoraussetzungen sind, muss der Induktionsanfang auch für zwei Aussagen bewiesen werden (n = 1 und n = 2).)

Beziehungsweise in meiner Wahl der Indizes

\( 1 \leq a_{n+2} \leq 2^{n+2} \)

mit Hilfe der Induktionsvoraussetzungen \( 1 \leq a_{n} \leq 2^{n} \) und \( 1 \leq a_{n+1} \leq 2^{n+1} \).

MfG

Mister

---

Ich glaub ich steh ein bisschen auf dem Schlauch:

a_n+1 = a_n-1 + a_n

n = 1  1 ≤ a_n-1 ≤ 2^n-1 => 1 ≤ 1 ≤ 1

n = 2  1 ≤ a_n ≤ 2ⁿ ⇒ 1 ≤ 2 ≤ 2

n -> n+1  1 ≤ a_n+1 ≤ 2ⁿ⁺¹ ⇒ 1 ≤ a_n-1 + a_n ≤ 2*2ⁿ

Soweit wie vorher, kann ich nun aber nicht sagen, dass

a_n-1, a_n, 2 und 2ⁿ

alle inder Induktionsvoraussetzung (n=1 und n=2) richtig waren?

 

Danke für deine Hilfe!

---

Ja, kannst du sagen. Insofern ist dein Induktionsschritt sogar richtig:

"n→n+1 (n+1) ≤ a_n+1 ≤ 2ⁿ⁺¹ ⇒  (n+1) ≤ a_n-1 +a_n ≤ 2* 2ⁿ"

Das "⇒" ist allerdings äußerst missverständlich verwendet. Du solltest eine andere Notation wählen. Genau genommen wäre die Vertauschung der Aussagen oder das Umdrehen des Pfeils exakt:

\( n+1 \leq (n - 1) + n \leq a_{n-1} + a_n \leq 2 \cdot 2^n = 2^{n+1} \Rightarrow n+1 \leq a_{n+1} \leq 2^{n+1} \).

Wenn ich genauer überlege, hat eigentlich nur dein falsch gesetzter Pfeil "⇒" für Verwirrung gesorgt. Ich nehme mal an, dass der Gedankengang richtig ist, bzw. deinem Groschen der Fall kurz bevorstand :) . Also: Pfeil einfach umdrehen: ⇐.

---

Ich glaube ich verstehe, dass ich in die falsche Richtung "gefolgert" habe.

Warum aber hast du nun mein "1" mit einem "n+1" ausgewechselt?

Und den zwischenschritt "≤ (n−1)+n" verstehe ich auch nicht ganz...

---

Die zu beweisene Aussage ist ja "n ≤ a_n ≤ 2^n".

Der Zwischenschritt "n + 1 ≤ (n−1)+n" ist aber ein nicht schwer zu verstehender Zwischenschritt.

---

Hallo Mister

"n + 1 ≤ (n−1)+n" verstehe ich ohne Problem.

Bei "(n−1) + n ≤ an−1 + an" kann ich aber nur erkennen, dass die die Werte links der Ungleichung gleich der Indices rechts der Ungleichung sind. Der Gedanke dahinter erschliesst sich mir aber momentan nicht.

---

Da gilt \( n - 1 \leq a_{n - 1} \) und \( n \leq a_{n} \) (Induktionsvoraussetzungen), gilt auch die Summe dieser beiden Ungleichungen: \( (n - 1) + n \leq a_{n - 1} + a_{n} \).