Vollständige Induktion mit Fibonacci Zahlen. Behauptung a(n)<(7/4)^n

Question

Angabe: a(1)=1, a(2)=2,    a(n+1)=a(n)+a(n-1), für n>=2,

zu zeigen: a(n)<(7/4)^n

Beweis:

IA:  1<7/4 w.A.

IS:  a(n+1)<(7/4)^{n+1}

a(n-1)<(7/4)^{n-1}

a(n)<(7/4)^n

(I): a(n+1)<(7/4)^{n-1}+(7/4)^n

(II):a(n+1)<(7/4)^n*(1+4/7)

(III):a(n+1)<(7/4)^n*(11/7)

(IV):(7/4)^n*(11/7)<(7/4)^n*(7/4)       -->

(V):a(n+1)<(7/4)^{n+1}            q.e.d

Kann mir jemand erklären, wie man von Zeile (I) auf Zeile (II) kommt?

Wieso kann man statt +(7/4)^{k-1} einfach *(1+4/7) schreiben?

Comments

Der IA ist falsch.

---

Wie ist der dann richtig?

wenn ich es mit a(1), a(2) und a(3) mache?

---

a(3) muss im IA nicht nachgewiesen werden, denn es folgt aus dem Induktionsbeweis.
Aber a(2) muss neben a(1) extra gezeigt werden, denn es wird in der Zeile " a(n)<(7/4)ⁿ  " verwendet.

Answer 1

Rechne den Schritt mal rückwärts:

(7/4)ⁿ*(1+4/7)

= (7/4)^n + (7/4)^n * (4/7) 

= (7/4)^n + (7/4)^n * (7/4)^{-1} 

= (7/4)^n + (7/4)^{n-1}  

Tipp: Schreib dir immer auch die Induktionsbehauptung von Anfang an hin. Damit du weisst wohin die Rechnung gehen soll:

IB: a(n+1)<(7/4)ⁿ⁺¹   

Comments

hab noch eine Frage: Stimmt der Beweis sonst grundsätzlich? Weil eigentlich habe ich in diesem Beweis das a(1) und a(2) gar nicht verwendet?

---

Definition Fibonnacci-Folge: a(1)=1, a(2)=2,    a(n+1)=a(n)+a(n-1), für n>=2,

zu zeigen: a(n)<(7/4)ⁿ

Beweis:

Verankerung: a_(1) = 1<7/4   stimmt.

a_(2) = 2 < (7/4)^2 = 3.0625  stimmt.

a_(3) = 3 < (7/4)^3 > (7/4)^2 stimmt.

IS:

Induktionsvoraussetzung

 a(n)<(7/4)^{n   .}

a(n-1)<(7/4)^n-1

Induktionsbehauptung a(n+1)<(7/4)ⁿ⁺¹

Beweis des Induktionsschritts

a(n)<(7/4)ⁿ

(I): a(n+1) = a(n-1) + a(n) <(7/4)^n-1+(7/4)ⁿ

(II):a(n+1)<(7/4)ⁿ*(1+4/7)

(III):a(n+1)<(7/4)ⁿ*(11/7)

(IV):(7/4)ⁿ*(11/7)<(7/4)ⁿ*(7/4)  Wie kommst du auf diese Zeile? 

      -->   Was bedeutet dieser Pfeil? 

(V):a(n+1)<(7/4)ⁿ⁺¹            q.e.d

---

naja man bekommt aus Zeile (III) dass a(n+1)<(7/4)^n*(11/7) ist, und (7/4)^n*(11/7) ist mit Sicherheit kleiner als (7/4)^n*(7/4) und daraus folgt(-->) dass a(n+1) auch mit Sicherheit kleiner als (7/4)^n*(7/4) ist und damit ist der Beweis fertig weil (7/4)^n*(7/4) ist ja (7/4)^n+1, somit ist a(n+1)<(7/4)^n+1 und das war ja zu beweisen!

Also so habe ich mir das gedacht

---

 (7/4)ⁿ*(11/7) ist mit Sicherheit kleiner als (7/4)ⁿ*(7/4)   

Ok. Das stimmt ja: https://www.wolframalpha.com/input/?i=(11%2F7)+%3C(7%2F4)

Schreibe über das entsprechende Zeichen ^{(11/ 7 < 7/4)}  so ist die Begründung vollständig sichtbar.

Zudem  würde ich III und IV in eine Zeile schreiben, damit die Kette mit < und = vollständig bleibt.

(III):a(n+1)<(7/4)ⁿ*(11/7) < (7/4)^n * (7/4) = (7/4)^{n+1}

(V):a(n+1)<(7/4)ⁿ⁺¹            q.e.d

---

oke das werd ich machen, vielen vielen Dank :)