Limit of the Fibonacci Ratio
The Fibonacci sequence is defined by $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$, giving the familiar $0, 1, 1, 2, 3, 5, 8, 13, 21, \ldots$
Does the ratio of consecutive terms $\dfrac{F_{n+1}}{F_n}$ converge as $n \to \infty$? If so, find the limit to the nearest thousandth. If not, report $-1$.
Hints
- Compute a few terms of the ratio $F_{n+1}/F_n$ -- do they appear to converge? If so, call the limit $L$ and try to derive an equation for it.
- Apply the recurrence $F_{n+1} = F_n + F_{n-1}$ in the numerator, then divide top and bottom by $F_n$. What does $F_{n-1}/F_n$ equal in the limit?
- You should arrive at $L = 1 + 1/L$, which gives $L^2 - L - 1 = 0$. Solve and discard the negative root using the fact that all Fibonacci terms are positive.
Worked Solution
How to Think About It: Start by just computing a few ratios: $1/1 = 1$, $2/1 = 2$, $3/2 = 1.5$, $5/3 \approx 1.667$, $8/5 = 1.6$, $13/8 = 1.625$, $21/13 \approx 1.615$. The ratios clearly converge -- they are bouncing around some value near $1.618$. At a whiteboard you can report $\approx 1.618$ with confidence immediately. The question is: how do you derive it cleanly?
Quick Estimate: By $n = 10$ we have $F_{11}/F_{10} = 89/55 \approx 1.6182$. The convergence is fast -- within a few iterations you are already within $0.01$ of the true limit. So the answer is somewhere around $1.618$.
Approach: Assume the limit $L$ exists and is positive. Use the recurrence relation to build a self-referential equation for $L$, then solve it.
Formal Solution:
Assume the limit $L = \displaystyle\lim_{n \to \infty} \dfrac{F_{n+1}}{F_n}$ exists and is finite. Apply the recurrence $F_{n+1} = F_n + F_{n-1}$ to the numerator:
$$L = \lim_{n \to \infty} \frac{F_{n+1}}{F_n} = \lim_{n \to \infty} \frac{F_n + F_{n-1}}{F_n} = 1 + \lim_{n \to \infty} \frac{F_{n-1}}{F_n}$$
The remaining limit is $\displaystyle\lim_{n \to \infty} \dfrac{F_{n-1}}{F_n}$, which is the reciprocal of $L$ (the index shift by 1 is immaterial since the limit is stationary). So:
$$L = 1 + \frac{1}{L}$$
Multiply through by $L$:
$$L^2 = L + 1 \implies L^2 - L - 1 = 0$$
The quadratic formula gives:
$$L = \frac{1 \pm \sqrt{5}}{2}$$
The two roots are approximately $1.618$ and $-0.618$. Since every Fibonacci term is positive (for $n \geq 1$), the ratio $F_{n+1}/F_n$ is always positive, so $L > 0$. We take the positive root:
$$L = \frac{1 + \sqrt{5}}{2} \approx 1.618$$
Answer: The limit exists and equals the golden ratio $\varphi = \dfrac{1 + \sqrt{5}}{2} \approx \mathbf{1.618}$.
Intuition
This problem illustrates a powerful technique: if a sequence is defined by a recurrence and you assume the limit exists, you can plug the limit into the recurrence and solve for it algebraically. The assumption of existence is doing real work -- it converts an infinite-limit problem into a finite algebraic one. (You can verify existence separately via monotone subsequences or the Binet formula, but in an interview, stating the assumption and solving is usually enough.)
The golden ratio $\varphi \approx 1.618$ shows up everywhere in mathematics and nature, but its appearance here has a clean algebraic reason: it is the unique positive solution to $x^2 = x + 1$, which is precisely the Fibonacci recurrence rewritten as a fixed-point equation. In quant work, this same trick -- assume a stationary distribution or limiting ratio exists, write a self-consistency equation, solve -- appears in Markov chain stationary distributions, Kelly criterion derivations, and certain option pricing recursions.