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!

Homework Help: Use iteration to guess an explicit formula

  1. Oct 11, 2016 #1
    1. The problem statement, all variables and given/known data

    Use iteration to guess an explicit formula for u_k = u_{k−2} * u_{k−1}, for all integers k ≥ 2, u_0 = u_1 = 2 and prove it .

    2. Relevant equations

    Hint: Express the answer using the Fibonacci sequence.

    3. The attempt at a solution

    u_k = u_{k−2} * u_{k−1} and u_0 = u_1 = 2, so

    u_2 = 2^2

    u_3 = 2^3

    u_4 = 2^5

    u_5 = 2^8

    u_6 = 2^13

    u_7 = 2^21

    Then (I think) in general we have ,

    2^{F_k} = 2^{F_k-1 + F_k-2}

    Not finished yet... But does it make sense so far?

    BTW, I tried putting $ signs around expressions, but mathjax(?) doesn't seem to render in preview.
  2. jcsd
  3. Oct 11, 2016 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    That was dollar signs in pairs, right? $$latex$$. Not sure if mathjax is same as LaTeX.
  4. Oct 11, 2016 #3
    Oh, I never knew you had to put the dollar signs in pairs. Thanks.

    $$2^{F_k} = 2^{F_{k-1} + F_{k-2}}$$ then $$2^{F_n} = 2^ {\frac{\frac {1 + \sqrt 5}{2} - \frac {1 + \sqrt 5}{2}}{\sqrt 5}}$$ which implies $$\log_22^{F_n} = \log_22^ {\frac{\frac {1 + \sqrt 5}{2} - \frac {1 + \sqrt 5}{2}}{\sqrt 5}}$$ meaning $$F_n = {\frac{\frac {1 + \sqrt 5}{2} - \frac {1 + \sqrt 5}{2}}{\sqrt 5}}$$

    Can I claim this to be the solution to the given recurrence relation?
  5. Oct 11, 2016 #4

    Charles Link

    User Avatar
    Homework Helper
    Gold Member

    Suggest you google Fibonacci series. I think you might have already solved this one as much as you can in post #1. (You still need to prove that your guess is correct.)
    Last edited: Oct 11, 2016
  6. Oct 11, 2016 #5
    I was unsure. Usually when we find an explicit formula for a recurrence, we get rid of indices in the recurrence relation so that we do at most one substitution into the formula. But if you say I am done - I am happy to take a break :) As for the proof, I think induction should take care of it. Thanks.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted