Solve this recursion

Question

\begin{cases} T(1) = 1 \\ T(n) = 2T(n-1)-4 \end{cases} Solve this recursion using summation factor method or iterative method. Could someone solve for me this recursion and explain all steps?

Answer 1

$$T(n)=2T(n-1)-4$$

$$T(n-1)=2T(n-2)-4$$

$$T(n-2)=2T(n-3)-4$$

$$\dots$$

$$T(n-i)=2T(n-(i+1))-4$$

SO:

$$T(n)=2(2T(n-2)-4)-4=2^2T(n-2)-2 \cdot 4-4=2^2(2T(n-3)-4)-2 \cdot 4-4=2^3T(n-3)-2^2 \cdot 4- 2 \cdot 4-4= \dots= 2^iT(n-i)- \sum_{k=0}^{i-1} 2^k \cdot 4$$

The recursions ends for $n-i=1 \Rightarrow i=n-1$.

Can you continue?

Answer 2

Because of the $2T(n-1)$ it almost looks like $T(n)$ will be roughly $2^{n-1}$ (I use $n-1$ because $T(1)$ is $1$ not $2$).

So let$$R(n) = 2^{n-1}R(n)$$ The recursion becomes $$ 2^{n-1}R(n) = 2\cdot 2^{n-2}R(n-1) -4 \\ R(1) = 1 $$ Divide thru by $2^{n-1}R(n) $ to get $$ R(n) = R(n-1) - \frac{4}{2^{n-1}} $$ So $$R(n) = 1 - \sum_{k=2}^n\frac{4}{2^{k-1}} = 1 - 4\sum_{j=1}^{n-1}\frac{1}{2^{j}} = 1 - 4 \left( 1 - \frac{1}{2^{n-1}}\right) = \frac{1}{2^{n-3}} - 3 $$ And substitute back: $$ T(n) = 2^{n-1} \left( \frac{1}{2^{n-3}} - 3 \right) = 4 - 3\cdot 2^{n-1} $$