Ungleichung mit Rekursion per Induktion beweisen

Question

Ich soll folgende Ungleichung mittels Induktion beweisen:

Die Formel  a(n) = 2a(n-1) + 3a(n-2)

gilt für alle n ≥ 2 mit a(0) = 1 und a(1) = 2  n∈ℕ₀

Und ist ≥ eⁿ für alle n ≥ 4

Den Induktionsanfang mit n = 4 habe ich problemlos hinbekommen, doch vor allem die Rekursion (in Kombination mit der Ungleichung) macht mir Schwierigkeiten.

Wie kann ich solche Formeln generell angehen?

Answer 1

Induktionsanfang: \(a(4)=61>e^4\) stimmt.

Induktionsvoraussetzung: \(\exists n\in \mathbb{N}_{\geq 4}: a(n)=2a(n-1)+3a(n-2)\geq e^n\)

Induktionsschritt:

Da \(3e^{-1}+2>e\) gilt:$$a(n+1)=2a(n)+3a(n-1)\geq 2e^{n}+3e^{n-1}=(3e^{-1}+2)e^n\geq e^{n+1}$$

Comments

Woher bekomme ich da das 3e^-1 + 2 > e ?

---

Du weißt: e<3 und damit: 1/e>1/3

3e^{-1}+2>1+2=3>e

Answer 2

Induktionsanfang
a(0) = 1
a(1) = 2
a(2) = 2·a(1) + 3·a(0) = 2·2 + 3·1 = 7
a(3) = 2·a(2) + 3·a(1) = 2·7 + 3·2 = 20
a(4) = 2·a(3) + 3·a(2) = 2·20 + 3·7 = 61 > e^4 = 54.60
a(5) = 2·a(4) + 3·a(3) = 2·61 + 3·20 = 182 > e^5 = 148.4


Induktionsschritt
a(n) ≥ 2·a(n - 1) + 3·a(n - 2)
a(n) ≥ 2·e^(n - 1) + 3·e^(n - 2)
a(n) ≥ 2/e·e^n + 3/e^2·e^n
a(n) ≥ (2/e + 3/e^2)·e^n
a(n) ≥ 1.142·e^n
a(n) ≥ e^n

Comments

Im Induktionsschritt zeigst du a(n+1)≥e^(n+1)?

---

Ich habe nur eine kleine Frage: Warum machst du den Induktionsschritt mit \(n\) anstatt mit \(n+1\)? Sollte man nicht im Induktionsschritt die Aussage für \(n+1\) zeigen, da man ja in der Induktionsvoraussetzung annimmt, dass die Aussage für ein beliebig festes \(n\) gilt und jetzt auf \(n+1\) schließen muss?

Sry, nicht gesehen. Racine hatte die selbe Frage

---

Nein. ICH zeige dass a(n) >= e^(n) unter der Annahme dass es schon für a(n - 1) und a(n - 2) gegolten hat.

Es ist im Grunde egal. Ich kann auch überall n durch n + 1 ersetzen. aber was gewinnt man dadurch?

Wichtig ist aber meiner Meinung nach dass ich es in der Induktionsannahme z.B. für a(4) und a(5) zeige und daraus schlussfolgere das es auch für a(6) gilt.

Bei mir gilt im Induktionsschritt also n >= 6!

---

Ja, gut, wohl wahr - war nur etwas verwirrend. Man kann auch von n-1 auf n schließen.

n>=720? Scherz.

---

Lach. Es stand mal in einer Klassenarbeit für die Mittelstufe

aus 4 werden 5!

Ο Das sind 20% mehr
Ο Das sind 25% mehr
Ο Man kann die prozentuale Erhöhung nicht bestimmen.

Kreuze die richtige Antwort an. Natürlich denke hier nur ein Mathematiker an 5! = 120 ;)

---

Ja, ok. War nur verwirrt, weil die Induktionsvoraussetzung nicht dort stand.

Ja, die guten alten Satzzeichen am Ende einer Formel sind immer sehr schwierig zu interpretieren. Da kann ich ein Lied von singen. Am Schlimmsten ist es, wenn sowas in der Klausur passiert und man den Übungsleiter in der Klausur nerven muss.