2

Suppose $f(n)=3f(\frac{n}{2})+1$ when n is even, and $f(1)=5$, please find $f(2),f(4),f(10),f(14)$ and so on.

I did $f(2)$ and $f(4)$ and answer is 16 and 49. But I am not sure if I am right about $f(10)$. So far I did:

$f(10)=3f(5)+1 = 2(3f(2)+1)+1 = 99.$ My friend got answer 143 and he is also not sure if the answer is correct. Can anyone help me understand how it is done correctly? Please.

Quality
  • 5,527
PeaceKing
  • 67

1 Answers1

0

This seems to be a recursive formula defining the terms of a sequence. lets evaluate the first few terms and see if we notice a pattern,

We have, $$f(n)=3f(\frac{n}{2})+1$$

$f(2)=16$

$f(4)=49$

$f(8)=148$

we have $f(2^n)=$

suppose $m=2^n$

then $f(m)=3f(2^{n-1})+1$

Do you notice anything?

Quality
  • 5,527
  • f(8)=3f (4) + 1 = (3 *49+ 1) + 1 = 149 . I think I am close but still I little confuse. f(n)=3f(n/2)+1 since this is the case, don't I need to at 1 to 148. – PeaceKing Apr 29 '15 at 19:07
  • Well you said f(4)=49, so f(8)= (3)(49)+1=147+1=148 – Quality Apr 29 '15 at 19:09
  • I think I got it. f(10)= 3((f4) +f(1)) + 1 = 3 * (49 + 5) +1 = 163. Correct? So my friend was right. – PeaceKing Apr 29 '15 at 19:18