Solving recurrence relation by iteration given an n

Question

Hello I have this problem: Assume $n=4^k$ (i.e., $k=\log_4 n$) for some $k$. And I have been instructed to solve by iterating through the recursion.

$$f(n)=\left\{\begin{array}{ll} 1&\mbox{if $n=1$}\\ 3f({n\over4})+n&\mbox{if $n\ge2$} \end{array} \right.$$

I am unsure whether to plug $4^k$ into n and then do k+1, or what are my other options. I do not what a "solution" to this type of problem would look like as well.

Answer 1

Plug in $n=4^k$. $$f(4^k)=\left\{\begin{array}{ll} 1&\mbox{if $k=0$}\\ 3f({4^{k-1}})+4^k&\mbox{if $k\ge1$} \end{array} \right.$$

For cases $k\geq1$, divide both sides by $4^k$. $$\frac{f(4^k)}{4^k}=\frac{3}{4}\frac{f(4^{k-1})}{4^{k-1}}+1$$ Now substitute $g(k)=\frac{f(4^k)}{4^k}$ then $$g(k)=\frac{3}{4}g(k-1)+1, \quad g(0)=1$$ Subtract $4$ from both sides, $$g(k)-4=\frac{3}{4}g(k-1)-3=\frac{3}{4}\left(g(k-1)-4\right)$$ Thus $g(k)-4$, if you interpret this as a sequence, is a geometric sequence with common ratio $\frac{3}{4}$.

Using the value of $g(0)$ and substituting back to $f(n)$ will give you the final answer.

---

Solving for $g(k)$ gave me $$g(k)=4-3\left(\frac{3}{4}\right)^k =\frac{f(4^k)}{4^k}$$ Substitute back $k=\log_4$, $$f(n)=4n-3n^{\log_4{3}}$$

Answer 2

Guide:

Yes, substitue $n=4^k$ and perhaps use induction on $k$.

$$f(4)=3f(1)+4=3+4$$

$$f(16)= 3f(4)+16=3(3+4)+16=3^2+3\cdot 4+16$$

$$f(64)=3f(16)+64=3(3(3+4)+16)+64=3^3+3^2\cdot 4+3\cdot 4^2+4^3$$

Geometric series might help.