Rekursionsgleichung per Induktion

Question

Sei \( n=4^{k} \) :

\( T(n)=\left\{\begin{array}{cc} c & \text { falls } n=1 \\ 3 T\left(\frac{n}{4}\right)+n & \text { falls } n>1 \end{array}\right. \)

Kann mir das mit dem Master Theorem erklären aber wie löse ich das per Induktion ?

Comments

Hallo

Was ist die Aufgabe? suchst du eine explizite Darstellung von T(n) und hast die gefunden und willst sie per Induktion beweisen, dann ist das doch einfach In T(n+1) T(n) einsetzen  und zeigen dass deine geratene Formel stimmt.

lul

---

Ja wir suchen eine geschlossene Form für T(n) durch substituieren :)

---

Hallo

hast du ne Formel und willst sie beweisen oder suchst du die Formel?

was heisst:"Kann mir das mit dem Master Theorem erklären"

schreib die ersten T(4^0) bis T(4^4) hin und sieh ob du dann auf 4^n verallgemeinern kannst.

Gruß lul

---

Ich soll diese Gleichung beweisen und das am besten per Induktion xD

---

Hallo

dann schreib deine Gleichung mal hin.

lul

---

also mit n+1 gelange ich dann zu

T(n+1) = 3T (4^k+1 / 4) + 4^k+1

---

Hallo
das ist ja die Rekursionsformel, was du beweisen sollst ist, dass die explizite Formel diesem Gesetz folgt. die Rekursionsfolge ist gegeben, die kann man nicht beweisen.
Hast du nun versucht eine explizite Formel zu finden?
Gruß lul

---

Mit   α = log₄ 3   wird   T(n)  =  n^α·(c-4) + 4n