Vollständige Induktion Abbildung

Question

ich suche nach einem Denkanstoß für die folgende Aufgabe. Hoffentlich könnt ihr mir helfen!

Beweisen Sie mittels vollständiger Induktion die folgende Aussage:

Die Abbildung T: ℕ-> ℕ sei gegeben durch T(1) = 1 und T(n) = T(n-1) + n für n >= 2. Es gilt T(n) =< n² für alle n ∈ℕ.

Da wir Abbildungen noch nicht durchgenommen haben, frage ich mich, ob das überhaupt etwas zur Sache tut bei dieser Aufgabe. Liege ich außerdem richtig damit, dass der Induktionsanfang in diesem Fall bei n=2 liegt?

für die Hilfe!

Comments

Falscher Kommentar

Answer 1

nee IA natürlich bei n =1 möglich. Beim Induktionsschritt gehe davon aus, dass deine IV für n-1 gilt und zeige, dass sie auch für n gilt. Dabei natürlich verwenden, dass \( T(n-1) \leq (n-1)^2\) nach IV gilt.

Ups das war wohl schon mehr als ein Anstoss ;).

Gruß

Comments

Danke, das hat mir schon sehr weitergeholfen! :)

Ich hänge jetzt noch an einer Sache fest. Du hast gesagt ich soll die IV

T(n − 1) ≤ (n − 1)² verwenden. Heißt das, ich kann T(n − 1) und T(n) durch (n − 1)² bzw. n² ersetzen?

---

Nein nicht ersetzen sondern damit abschätzen!

---

Ah, ich glaube, ich hab es:

T(n − 1) = T(n − 2) + 2n − 1    ≤ n²- 2n + 1

T(n)       = T(n − 1) + n              ≤ n²

Ich sehe auf jeden Fall den Zusammenhang.

Ich muss jetzt nur noch irgendwie umformen und dann hab ich alles, richtig?

---

Warum setzt du T(n-1) nochmals ein (deine 1. Gleichung)?

Nach IV ist ja

T(n) = T(n-1)+n ≤(n-1)^2+n

und warum das am Ende kleiner als n^2 ist darfst du nun argumentieren.

---

Ah, alles klar, ich hab jetzt alles :)

Vielen Dank für deine Hilfe!