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, since every ratio is at least $1$. Then show the limit exists: bound $|r_n - \varphi|$ by $|r_{n-1} - \varphi|/\varphi$, where $r_n = F_{n+1}/F_n$.
Worked Solution
How to Think About It: The question has two parts: does the limit exist, and what is it? Use the fixed-point heuristic: write the ratio as a one-step recursion, solve $L = 1 + 1/L$ for the candidate, then show the recursion really pulls you there. The second step is what actually answers "does it converge?". Algebra alone cannot do it: $x_{n+1} = 2x_n$ has the fixed point $0$, yet it diverges from $x_0 = 1$.
Quick Estimate: Compute the 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$. They alternate above and below some value, and the gaps between neighbors are $1$, $0.5$, $0.167$, $0.067$, $0.025$, $0.01$, each about $2.6$ times smaller than the last. So they close in on a single number. By $n = 10$ we have $F_{11}/F_{10} = 89/55 \approx 1.6182$, so the answer is near $1.618$.
Approach: Turn the ratio into a recursion, find its only admissible fixed point, then show the distance to that point shrinks geometrically.
Formal Solution:
Step 1: the recursion. Let $r_n = F_{n+1}/F_n$ for $n \geq 1$, so $r_1 = 1$. Dividing $F_{n+1} = F_n + F_{n-1}$ by $F_n$ gives
$$r_n = 1 + \frac{F_{n-1}}{F_n} = 1 + \frac{1}{r_{n-1}} \quad (n \geq 2).$$
The sequence $F_1, F_2, \ldots$ is positive and non-decreasing, so $r_n \geq 1$ for every $n$.
Step 2: the only possible limit. If $r_n \to L$, then $L \geq 1$, and passing to the limit in the recursion gives $L = 1 + 1/L$, that is
$$L^2 - L - 1 = 0 \implies L = \frac{1 \pm \sqrt{5}}{2}.$$
The roots are about $1.618$ and $-0.618$. Since $L \geq 1$, the only candidate is $\varphi = \frac{1 + \sqrt{5}}{2}$.
Step 3: the limit exists. The candidate satisfies $\varphi = 1 + 1/\varphi$. Subtract this from the recursion:
$$|r_n - \varphi| = \left|\frac{1}{r_{n-1}} - \frac{1}{\varphi}\right| = \frac{|r_{n-1} - \varphi|}{r_{n-1}\,\varphi} \leq \frac{|r_{n-1} - \varphi|}{\varphi},$$
using $r_{n-1} \geq 1$. Each step divides the error by at least $\varphi$. Since $|r_1 - \varphi| = \varphi - 1 = 1/\varphi$, this gives $|r_n - \varphi| \leq \varphi^{-n}$, which tends to $0$. So the ratio converges, and its limit is $\varphi$.
Check with Binet's formula: $F_n = (\varphi^n - \psi^n)/\sqrt{5}$ with $\psi = -1/\varphi$, so
$$\frac{F_{n+1}}{F_n} = \varphi \cdot \frac{1 - (\psi/\varphi)^{n+1}}{1 - (\psi/\varphi)^n} \to \varphi,$$
because $|\psi/\varphi| = 1/\varphi^2 \approx 0.382$. That is also why the gaps in the Quick Estimate shrink by about $2.6 = \varphi^2$ per step.
Answer: Yes, the ratio converges, to 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, plug a limit into the recurrence and solve for it algebraically. That step only produces a candidate, because it assumes the limit exists. The second step is to show that iterating the recurrence contracts toward the candidate. Here each step divides the distance to $\varphi$ by at least $\varphi$, so the proof takes two lines.
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, the same pair of steps (write a self-consistency equation, then check that iterating it converges) appears in Markov chain stationary distributions and in fixed-point calibration routines.