Induktion nicht-negative Funktion

Question

Text erkannt:

Sei \( f: \mathbb{N} \rightarrow \mathbb{R}_{+} \) eine nicht-negative Funktion und \( T(1)=b \) und \( T(n)=a T(n / c)+f(n) \) für Konstanten \( a, b, c>0 \).
1. Zeigen Sie per Induktion, dass wenn \( f(1)=b \) gilt, es für alle \( n=c^{k} \) mit \( k \in \mathbb{N} \) folgt, dass \( T(n)=\sum \limits_{i=0}^{k}\left(a^{i} \cdot f\left(\frac{n}{c^{i}}\right)\right) . \)

Kann mir jemand bitte zeigen wie die Induktion hier geht?
Mit freundlichen Grüßen

Comments

Hallo

setze n=c^k und Induktion über k

Gruß lul

---

Danke dir lul,

wie genau würde der Induktionsanfang dann aussehen? Möchte nichts falsch machen und mit Falschem weiterrechnen, deswegen wär es lieb wenn du es mir kurz zeigen könntest.

---

wie genau würde der Induktionsanfang dann aussehen? Möchte nichts falsch machen und mit Falschem weiterrechnen, deswegen wär es lieb wenn du es mir kurz zeigen könntest.

Wenn du einen Ansatz hast, dann zeig ihn doch. Dann können wir sagen ob es richtig ist.

Induktionsanfang ist doch einfach nur, dass man zeigen soll das es für k = 0 alco n = c^0 = 1 gilt.

Hier sollst du aber Annehmen das T(1) = b gilt.

---

IA: Für k = 0 gilt T(c^k) = T(c^0) = T(1) = b

Und da T(1) = b feststeht, ist der Induktionsanfang abgeschlossen.

Ist es so richtig?

---

Ja. Das ist richtig.

Jetzt fehlt nur noch die Induktion.

Unter der Voraussetzung das es für ein beliebiges k gilt sollst du jetzt zeigen, dass es auch für k + 1 gilt.

---

Dankeschön, aller Anfang ist schwer :D