Use iteration to guess an explicit formula

[Arew]

Homework Statement

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 .

Homework Equations

Hint: Express the answer using the Fibonacci sequence.

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. [/B]

 

[haruspex]

But does it make sense so far?

Yes.

BTW, I tried putting $ signs around expressions, but mathjax(?) doesn't seem to render in preview.

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

 

[Arew]

Yes.

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

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?

 

[Charles Link]

Homework Statement

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 .

Homework Equations

Hint: Express the answer using the Fibonacci sequence.

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. [/B]

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.)

 

[Arew]

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.)

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.