Rekurrenzgleichung geschlossene Form

Question

Aufgabe 1 - Rekurrenz:

Für \( a, b \in \mathbb{N} \) sei die Rekurrenzgleichung \( T(0)=a, T(n)=T(n-1)+b \) für alle \( n \in \mathbb{N}_{>0} \) gegeben.
Finden Sie (ohne Anwendung des Mastertheorems) eine geschlossene Form für \( T \) und zeigen Sie formal, dass \( T \in \mathcal{O}(n) \) gilt.

Kann mir jemand bitte helfen? Vor allem beim Finden der geschlossenen Form.

Comments

Vom Duplikat:

Titel: Es geht um die folgende Rekurrenzgleichung, da ich es nicht verstehe und kann.

Stichworte: algorithmus,gleichungen

Für a,b∈N sei die Rekurrenzgleichung T(0)=a, T(n)=T(n−1)+b für alle n∈N>0 gegeben.
Finden Sie (ohne Anwendung des Mastertheorems) eine geschlossene Form für T und zeigen Sie formal, dass T∈O(n) gilt.

Answer 1

Aloha :)

Gegeben: \(\quad T(n)=T(n-1)+b\quad;\quad T(0)=a\quad;\quad n\in\mathbb{N_0}\)

Behauptung: $$T(n)=a+b\cdot n$$

Verankertung bei \(n=0\):$$T(n)=T(0)=a=a+b\cdot0=a+b\cdot n\quad\checkmark$$Induktionsschritt \(n\to n+1\):$$T(n+1)=T(n)+b\stackrel{I.V.}{=}(a+b\cdot n)+b=a+b\cdot(n+1)\quad\checkmark$$

Comments

Vielen Dank, du bist der Beste!