Vollständige Induktion: a(0) = 1 ; a(1) = 7 ; a(n+1) = 3·a(n) - 2·a(n-1)

Question

a₀=1, a₁=7

a_n+1=3*a_n - 2*a_n-1  für n>=1

Beweisen

1. a monoton wachsen a_n<=a_n+1

2. a_n ist stets ungerade 

3. es gilt immer a_n<= 6*2ⁿ

Answer 1

1. an ist monoton wachsed (an+1 ≥ an)

 

an+1 ≥ an

3·an - 2·an-1 ≥ an

2·an - 2·an-1 ≥ 0

2·(an - an-1) ≥ 0

an - an-1 ≥ 0 --> Das ist die Induktionsannahme und damit erfüllt.

 

2. an ist stets ungerade

 

an+1 ist ungerade wenn an und an-1 ungerade sind.

an+1 = 3·an - 2·an-1

an+1 = 3·(2·a - 1) - 2·(2·b - 1)

an+1 = 6·a - 3 - 4·b + 2

an+1 = 6·a - 4·b - 1

an+1 = 2·(3·a - 2·b) - 1 --> ungerade

Comments

Die 3) funktioniert so nicht, da a(n-1)> 6*2^{n-1} und nicht

---

Ja da sollte man noch a2 ausrechnen. Damit man 2 Werte hat für die es gilt.

---

Mit mehr Werten wird es nicht besser. Auf der Linken Seite wird ein Summand nach oben, der andere nach unten abgeschätzt. Und das liefert keine Abschätzung - weder nach oben noch nach unten- des ganzen Terms. Der einfachste Weg wär hier a(n)=6*2^n-5 zu zeigen.

---

Ja. Ich sehe meinen Fehler. Ok. Das wäre mit deiner Variante wohl am einfachsten. Aber wie kommt man am geschicktesten auf die Vermutung?

 

Einfach ein paar Folgeglieder ausrechnen? Oder über die direkte Wandlung der rekursiven Folge in einen expliziten Term?

 

3. Es gilt an ≤ 6·2n

Vermutung

an = 6·2^n - 5

Nachweis

an+2 = 3·an+1 - 2·an

6·2^{n + 2} - 5 = 3·(6·2^{n + 1} - 5) - 2·(6·2^n - 5)

24·2^n - 5 = 18·2^{n + 1} - 15 - 12·2^n +10

24·2^n = 36·2^n - 12·2^n

24·2^n = 24·2^n