Homework Help: Use iteration to guess an explicit formula

1. Oct 11, 2016

Arew

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. Oct 11, 2016

haruspex

Yes.
That was dollar signs in pairs, right? $$latex$$. Not sure if mathjax is same as LaTeX.

3. Oct 11, 2016

Arew

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?

4. Oct 11, 2016

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
5. Oct 11, 2016

Arew

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.