I am trying to solve the following recurrence relation:
$$ T(n) =\begin{cases} 4T(n-1) & \text{, if }n\gt1\\1 & \text{, if }n=1 \end{cases} $$ This is what I have got so far:
$$4T(n-1)+2$$ $$4^2T(n-2) +4\cdot2 +2$$ $$4^3T(n-3) + 4\cdot4\cdot2 +4\cdot2 +2$$ $$4^kT(n-k) + 2(k-2)+2(k-3)+2$$
Then I used $n-k =1$ to get $k = n-1$
So: $4^{n-1}T(n-(n-1)) + 2(n-3)+2(n-4)$. How many times I need to do this? $$4^{n-1}T(1)+\cdots$$ $$4^{n-1} + 2(n-3)+2(n-4)$$ How do I represent that second part? I am stuck on what to do next. Please help!
Assuming that the recurrence relation should be $T(n)=4T(n-1)+2$ for $n>1$, then we get $$ T(n)=4T(n-1)+2=4(4T(n-2)+2)+2=4(4(4T(n-3)+2)+2)+2=\cdots=4^{n-1}T(1)+4^{n-2}\cdot 2+4^{n-3}\cdot 2 +\cdots +2=\frac{1}{3}(5\cdot 4^{n-1}-2) $$ This formula can be proven formally by induction: it holds for $n=1$, and $$ T(n)=4T(n-1)+2=\frac{1}{3}(5\cdot 4^n-8)+2=\frac{1}{3}(5\cdot 4^n-2) $$ So it holds for all positive integers $n$.