How to solve the following with substitution…

Question

$T_{n} = 2T_{n-1} + 4$

I've tried substituting in $T_{n-1}$, $T_{n-2}$, etc, but I still don't know the pattern or general form. I am looking to solve this equation with the substitution technique.

Answer 1

Alt. hint:  divide by $2^n$ and write it as $\,\dfrac{T_n}{2^n}=\dfrac{T_{n-1}}{2^{n-1}}+ \dfrac{1}{2^{n-2}}\,$, telescope and sum the GP on the RHS.

Answer 2

$$T_n = 2T_{n-1} + 4$$

Start by looking at $T(1)$ $$T(1) = 2T(0) + 4 $$ Substitute in $T(1)$ into your expression for $T(2)$ $$T(2) = 2(2(T(0) + 4) + 4 $$ Simplify $$T(2) = 4T(0) + 8 + 4 $$ Thus we can extend this to the case of $T(n)$

$$T(n) = 2^{n}T(0) + \sum_{i=1}^{n} 2^{i} $$

Which gives you a big oh runtime of $$T(n) = 2^n $$

Answer 3

(Based on @Akababa's comment under the OP, and posted as CW.)

The recurrence has the constant solution $\,T_n=-4\,$, which suggests looking at the differences $\,T_n-(-4)\,$. That in turn leads to $\require{cancel}\,T_{n} \color{red}{+4} = 2T_{n-1} \color{red}{+8-\bcancel{4}}+ \bcancel{4}\,$ $\iff T_n+4 = 2(T_{n-1}+4)$. It follows that $\,T_n+4\,$ is a GP with common ratio $2$, so in the end $T_n+4 = 2^n(T_0+4)$.