Golden Fractions
Find the link between a sequence of continued fractions and the
ratio of succesive Fibonacci numbers.
Age
16 to 18
Challenge level
Here is a sequence of continued fractions: $$X_1=1, \quad X_2 = {1 \over 1+1}, \quad X_3 = {1\over\displaystyle 1+ { 1 \over \displaystyle 1+ 1}}, \quad X_4 = {1\over\displaystyle 1+ { 1 \over \displaystyle 1+ { 1\over 1 + 1}}} ,...$$ Notice that $$X_{n+1} = {1\over 1 + X_n}.$$ Now suppose that this sequence tends to a limit $L$ as $n\to \infty$ then put $X_{n+1}=X_n=L$ and prove that $L =\phi - 1 = {1\over \phi}$ where $\phi$ is the Golden Ratio, the positive solution to the equation $x^2 - x -1 = 0$.
Prove that $$X_n={F_n\over F_{n+1}}$$ where $F_n$ is a Fibonacci number from the sequence defined by the relation $F_{n+2}=F_{n+1}+F_n$ where $F_1=1$ and $F_2=1$.
Hence show that the ratio of successive terms of the Fibonacci sequence $${F_{n+1}\over F_n}$$ tends to the Golden Ratio as $n\to \infty$.
The hints are written into the question. If you can do a little simple algebra, solve quadratic equations and argue through a proof by induction, then you can sail through this question.
This solution came from Joseph of Colyton Grammar School. Also Yosef who has just graduated from High School and Andrei from Tudor Vianu National College, Bucharest, Romania sent in good solutions.
Supposing that the sequence of continued fractions does tend to a limit $L$ as $n \to \infty$ such that $X_{n+1} = X_n = L$ then, since $$X_{n+1} = {1\over 1+X_n },$$ we can say that: $L=1/(1+L)$ and therefore rearranging gives the quadratic equation $L^2+L-1=0$. Solving this using the quadratic formula gives $$L={-1+ \sqrt5 \over 2}$$ I discarded the negative root because the limit must be positive since we are summing positive fractions.
By taking the positive root of the equation $X^2-X-1=0$ I found the golden ratio $$\phi = {1+ \sqrt 5\over 2}$$ and so $$\phi -1 = {-1+ \sqrt5 \over 2} = L$$ and $${1\over \phi} = {2\over (1+ \sqrt 5)}.$$ By multiplying the numerator and the denominator by $1-\sqrt 5$: $$\eqalign { {1\over \phi} &= {2(1-\sqrt 5)\over(-4)} \cr &= {-1+ \sqrt 5\over 2} = L.}$$ Therefore the limit $L$ of the continued fraction $X_n$ (as $n\to \infty$) is equal to ${1\over \phi}$ where $\phi$ is the golden ratio.
I used induction to prove each continued fraction is equal to the ratio of two Fibonacci numbers, that is to prove the statement $P(n)$ given by $$P(n): X_n = F_n / F_{n+1}$$ where $F_n$ is a Fibonacci number from the sequence defined by the relation $F_{n+2}=F_{n+1}+F_n$ with $F_1=1$ and $F_2=1$.
$X_1 = 1$ and $F_1 /F_2 = 1/1 =1$, therefore $P(1)$ is true.
Assume that $P(k)$ is true, then $X_k = F_k / F_{k+1}$. By the recurrence relation for the continued fractions $X_{k+1} = 1/ (1 + X_k)$. Hence
$$\eqalign{ X_{k+1}&= {1\over 1+X_k} \cr &= {1\over 1+F_k/F_{k+1}} \cr &= {F_{k+1}\over F_{k+1} + F_k}.}$$
But by the recurrence relation for the Fibonacci sequence $F_{k+2} = F_{k+1} + F_k$ which gives $$X_{k+1}= {F_{k+1}\over F_{k+2}}$$ and hence $P(k+1)$ is true.
Therefore if $P(k)$ is true then $P(k+1)$ is true. But $P(1)$ is true and so, by the axiom of mathematical induction, $P(n)$ is true for all positive integers. So we have proved $$X_n = {F_n\over F_{n+1}}.$$ Since we have shown that the limit of $X_n$ (as $n\to \infty$) is $1/\phi$ we have now proved that the limit of $F_n/F_{n+1}= 1/\phi$ (as $n\to \infty$) and so the limit (as $n \to \infty$) of $F_{n+1} / F_n$ is $\phi$, the golden ratio.
Some very pretty results here! It should come as no surprise to see Fibonacci numbers linked with the Golden Ratio. This is the simplest of all infinite continued fractions and the sequence of approximants converges very rapidly to $\phi -1$.