A golden number

Probability Level 3

Suppose that you have a sequence of the type { F k } k ≥ 0 , \{F_k\}_{k \geq 0}, that obeys the rule :

F n = F n − 1 + F n − 2 ∀ n ≥ 2. F_n = F_{n-1}+F_{n-2} \quad \forall n \geq 2.

Suppose that F 0 , F 1 ∈ R 0 + F_0 , F_1 \in \mathbb R_0^{+} are given. Let ϕ n = F n F n − 1 \phi_n = \frac{F_n}{F_{n-1}} , n > 0 \ \ \ n >0 .
What is

ϕ = lim ⁡ n → ∞ ϕ n ? \phi = \lim_{n \rightarrow \infty} \phi_n?

Rounded your answer to the nearest thousandths.

NOTE : In regards to some complains I have had, I would like to stress that : ∀ n > 0 , ϕ n > 0 \forall n>0, \ \phi_n >0 .


The answer is 1.618.

View wiki
Patrick Bourg by Patrick Bourg , 28, United Kingdom

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

First of all, given the definition of { F k } k ≥ 0 \left \{ F_{k} \right \}_{k \geq 0} we are able to write, for n > 1 n > 1 that

F n F n − 1 = 1 + F n − 2 F n − 1 \frac{F_{n}}{F_{n-1}} = 1 + \frac{F_{n-2}}{F_{n-1}}

which implies that

lim ⁡ n → ∞ F n F n − 1 = ϕ = 1 + lim ⁡ n → ∞ F n − 2 F n − 1 \lim_{n\rightarrow \infty} \frac{F_{n}}{F_{n-1}} = \phi = 1 + \lim_{n\rightarrow \infty} \frac{F_{n-2}}{F_{n-1}}

For the remaining limit, we may argue that

lim ⁡ n → ∞ F n − 2 F n − 1 = 1 lim ⁡ n → ∞ F n − 1 F n − 2 \lim_{n\rightarrow \infty} \frac{F_{n-2}}{F_{n-1}} = \frac{1}{\lim_{n\rightarrow \infty} \frac{F_{n-1}}{F_{n-2}}}

And then making k = n − 1 ⇒ n − 2 = k − 1 k = n - 1 \;\;\; \Rightarrow \;\;\; n - 2 = k - 1 implies that

1 lim ⁡ n → ∞ F n − 1 F n − 2 = 1 lim ⁡ k → ∞ F k F k − 1 = 1 ϕ \frac{1}{\lim_{n\rightarrow \infty} \frac{F_{n-1}}{F_{n-2}}} = \frac{1}{\lim_{k\rightarrow \infty} \frac{F_{k}}{F_{k-1}}} = \frac{1}{\phi}

Therefore we get the second degree equation

ϕ = 1 + 1 ϕ \phi = 1 + \frac{1}{\phi}

which has the solution

ϕ = 1 + 5 2 \phi = \frac{1+\sqrt{5}}{2}

where we have disconsidered the "minus" solution because F n > F n − 1 F_{n} > F_{n-1} for every n > 1 n > 1 which is easily checked.

9 Helpful 0 Interesting 0 Brilliant 0 Confused

Do you know how to show that the limit ϕ \phi must exist and be finite?

Calvin Lin Staff - 6 years, 4 months ago

Log in to reply

Correct me if I'm wrong. I got a little bit confused doing this proof by induction. First of all, notice that the { F k } k ≥ 0 \left \{ F_{k} \right \}_{k\geq 0} sequence is an increasing sequence. The proof is given by induction observing that

F 2 = F 1 + F 0 > F 1 F_{2} = F_{1} + F_{0} > F_{1}

And now assume it is true for some k k . It follows

F k = F k − 1 + F k − 2 > F k − 1 > 0 F_{k} = F_{k-1} + F_{k-2} > F_{k-1} > 0

and therefore

F k + 1 = ( F k − 1 + F k − 2 ) + F k − 1 = F k + F k − 1 > F k F_{k+1} = \left ( F_{k-1} + F_{k-2} \right ) + F_{k-1} = F_{k} + F_{k-1} > F_{k}

since F k − 1 > 0 F_{k-1} > 0 . Now we know that this is an increasing sequence. But we actually want to prove that the limit of

F n F n − 1 \frac{F_{n}}{F_{n-1}}

exists, which is a sequence itself. But it suffices to observe that

F n F n − 1 = 1 + F n − 2 F n − 1 \frac{F_{n}}{F_{n-1}} = 1 + \frac{F_{n-2}}{F_{n-1}}

and as 0 < F n − 2 < F n − 1 0< F_{n-2} < F_{n-1} it follows that F n − 2 F n − 1 \frac{F_{n-2}}{F_{n-1}} is strictly decreasing and limited. Therefore F n F n − 1 \frac{F_{n}}{F_{n-1}} must have a nice value.

Lucas Tell Marchi - 6 years, 4 months ago

Log in to reply

Great! That's one approach to take.

Another would be to use the theory of linear recurrences to understand what F n F_n is, and to show that the limit is indeed ϕ \phi .

Calvin Lin Staff - 6 years, 4 months ago

this can simply be solved using fibonacci series answer is 'sigma'

Sukrut Waghmare - 6 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...