Hat irgendjemand eine Idee wie man das auflöst?

Question

Aufgabe:

Man zeige mittels vollständige Induktion, dass für die rekursiv definerte Folge x0=1 und x(k+1) = xk +18k+15 für k >= 0 allgemein gilt:

xn=(3n+1)^2 , für alle n>=0.
Problem/Ansatz:

Hat irgendjemand eine Idee wie man das auflöst? Ich habe schon mit vollständige Induktion gearbeitet aber das hier kann ich nischt schaffen, weil mir die Zusammenhang zwischen diese zwei Themen unklar ist.

Vielen Dank!

Answer 1

Wenn (1) x_n=(3n+1)² , dann (2) x_n+1=(3n+4)² ,

Setze (1) und (2) ein in x_n+1 = x_n+18n+15

und zeige die Gleichheit durch Auflösen der Klammern und Zusammenfassen.

Comments

Ok, jetzt habe ich das gemacht und beide Seiten sind gleich, aber welche Role spielt die rekursive Folge und x0 = 1 in der ganzen Aufgabe? Vielen Dank

---

Satz: Zu einer rekursiven Folgengeschreibung a_n+1=a_n+r(n) gibt es eine äquivalente explizite Darstellung a_n=g(n), wenn das Einsetzen von a_n (explizit) und a_n+1 (explizit) in die rekursive Darstelling zu einer wahren Aussage führt.

Answer 2

Wo siehst du den Zusammenhang nicht? Für den Beweis ist Induktion durchaus denkbar.
Induktionsanfang: Nach Definition der Folge ist x0 = 1. Prüfe also ob für n=0 auch die angegebene iterative Vorschrift \(x_n=(3n+1)^2\) zu 1 auswertet.
Induktionshypothese: Sei \(k\in \mathbb{N}\) fest. Dann gilt \(\forall n\in \mathbb{N}, \ 0\leq n \leq k: \ x_n=(3n+1)^2\).
Induktionsschritte: Überprüfe, ob für n->n+1 unter Voraussetzung der Induktionshypothese deine rekursive Vorschrift \(x_{n+1}=x_n+18n+15\) dasselbe Ergebnis liefert wie die zu zeigende iterative (für n+1): \(x_{n+1}=(3(n+1)+1)^2\).

Answer 3

x(0)=1 und

x(k+1) = x(k) +18k+15

für k >= 0 allgemein gilt:

$$ x(n)=(3n+1)^2 $$

 , für alle n>=0.

Induktions Anfang

$$ k=0 $$ $$ x(1)= x(0)+18*0+15=$$ $$ 1+18*0+15= 16 =$$ $$ 4^2=(3*1+1)^2$$

okay

Induktionsannahme

$$ x(n)=(3n+1)^2 $$ $$ x(n)+18n +15=$$ $$ (3n+1)^2 +18n +15$$ $$ x(n+1)= $$ $$ (3n+1)^2 +18n +15=$$ $$ 9n^2+6n+1+18n+15=$$ $$ 9n^2+24n +16=$$ $$ (3n +4)^2=$$ $$ (3(n+1)+1)^2$$

Induktionsschluss

wzzw