1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recurrence Relations, finding f(n)

  1. Dec 12, 2008 #1
    1. The problem statement, all variables and given/known data
    Find f(n) when n = 2^k, where f satisfies the recurrence realtion f(n) = f(n/2) +1 with f(1) = 1

    2. Relevant 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...
    3. 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?
  2. jcsd
  3. Dec 12, 2008 #2


    User Avatar

    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.
  4. Dec 12, 2008 #3


    User Avatar
    Science Advisor

    I would start by calculating some values. f(20)= f(1)= 1, f(21)= f(2)= f(1)+ 1= 2, f(22)= f(4)= f(2)+ 1= 3, f(23)= f(8)= f(4)+1= 4, f(24)= 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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Recurrence Relations, finding f(n)