0

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!

user127.0.0.1
  • 7,267
setlio
  • 105
  • 1
  • Is there a typo in your relation? Otherwise you should just guess (before iterating $T$ to find a closed form) $$ 1,4,16,64,256,\dots \qquad 4^0,4^1,4^2, $$ looks like $T(n)=4^{n-1}$ and indeed $$ 4T(n-1)=4 \cdot 4^{n-2} = 4^{n-1}=T(n) $$ – Blah Feb 11 '14 at 06:38
  • I suppose a typo in your post. Otherwise, where the $2$'s come from ? – Claude Leibovici Feb 11 '14 at 07:34

1 Answers1

0

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$.

pi37
  • 1,521
  • 7
  • 7