Exaktes Lösen der Rekursionsgleichung: t_{2}(n) = 4 + t_{2}(n - 2)

Question

Guten morgen

ich benötige Hilfe beim Lösen einer Rekursionsgleichung

t₂(0) = 1

 t₂(1) = 3

t₂(n) = 4 + t_{2}(n - 2)

Ich möchte sie gern exakt lösen.

Danke für eure Hilfe

Answer 1

t(n) = 2*n + 1

kannst du mit vollständiger Induktion beweisen.

Comments

wie kamst du drauf, dass man die Form so umstellen kann?

weil wenn man es aus multipliziert kommt man auf etwas anderes

Answer 2

t_{2}(0) = 1

t_{2}(1) = 3

t_{2}(n) = 4 + t_{2}(n - 2)

Rechne einige Werte aus:

t(0) = 1

t(2) = 3

t(3) = 1+4 = 5

t(4) = 3+4 = 7

t(5) = 5+4 = 9

t(6) = 7+4 = 11

nun hast du bestimmt eine Vermutung.

Dann kannst du einen Induktionsbeweis machen.

Comments

Du kannst häufig einen Integrationsschritt machen. Anfangsbedingungen beachten.

Hier zusätzlich berücksichtigen, dass die n in Zweierschritten wachsen. D.h. 4n wird zu 2n.

Nachtrag: Sagt dir "Mastertheorem" etwas? https://www.mathelounge.de/250381/master-theorem-rekursionsgleichung

---

ich habe jetzt lange die Induktion versucht, aber bin leider nicht auf ein Ergebnis gekommen. Kannst du mir noch n tipp bzw. hilfe geben?

---

Mache den Induktionschritt von n nach (n+2) 

Da braucht es dann zwei Fälle: 1. Fall n gerade, 2. Fall n ungerade.

---

also warum man die Fallunterschiedung macht ist mir klar, aber ich habe es heute jetzt nochmal probiert bin aber immer noch nicht auf 2*n+1 gekommen...

---

Die Verankerung für 2n+1 hat man bereits mit meiner Rechnung oben.

Was hast du denn nun im ersten Fall für die Induktionsvoraussetzung IV und was für die Induktionsbehauptung IB ?

---

Beim ersten Fall hab ich jetzt mal das n gerade is. Da wird ja immer t(0) am Ende hinzugefügt weil es ja quasi aufgeht.

Bei IB muss doch eig des 2n+1 hin