Recurrence Relations, finding f(n)

[ramenmeal]

Homework Statement

Find f(n) when n = 2^k, where f satisfies the recurrence realtion f(n) = f(n/2) +1 with f(1) = 1

Homework Equations

f(n) = a*f(n/b) + c
when n = b^k, where k is a positive integer,
f(n) = C1n^(log a base b) + C2

C1 = f(1) +c/( a-1) and C2 = -c/ (a-1)

keep in mind i may be trying to use the wrong equation...

The Attempt at a Solution

a =1, b = 2, c = 1

then C1 = 1+ 1/0 and C2 = -1/0

i'm not sure what i can do from here... c1 and c2 both include undefined #'s

perhaps I'm not even approaching the problem correctly?

 

[_k_]

Hi,
Now I am not sure if I understood it correctly, but it seems to be much simpler:
if n = 2^k and f(n) = f(n/2) + 1
f(n) = f(2^k) = f(2^(k-1)) + 1 = ... = f(2^(k-j)) + j

Now, the answer should be obvious.

 

[HallsofIvy]

I would start by calculating some values. f(2⁰)= f(1)= 1, f(2¹)= f(2)= f(1)+ 1= 2, f(2²)= f(4)= f(2)+ 1= 3, f(2³)= f(8)= f(4)+1= 4, f(2⁴)= f(16)= f(8)+ 1= 5. Looks obvious to me. Of course, you still have to prove that obvious "guess". Proof by induction should work.