Why does this process map every fraction to the golden ratio?

Start with any positive fraction $$\frac{a}{b}$$. First add the denominator to the numerator: $$\frac{a}{b} \rightarrow \frac{a+b}{b}$$ Then add the (new) numerator to the denominator: $$\frac{a+b}{b} \rightarrow \frac{a+b}{a+2b}$$ So $$\frac{2}{5} \rightarrow \frac{7}{5} \rightarrow \frac{7}{12}$$.

Repeating this process appears to map every fraction to $$\phi$$ and $$\frac{1}{\phi}$$:

$$\begin{array}{ccccccccccc} \frac{2}{5} & \frac{7}{5} & \frac{7}{12} & \frac{19}{12} & \frac{19}{31} & \frac{50}{31} & \frac{50}{81} & \frac{131}{81} & \frac{131}{212} & \frac{343}{212} & \frac{343}{555} \\ 0.4 & 1.40 & 0.583 & 1.58 & 0.613 & 1.61 & 0.617 & 1.62 & 0.618 & 1.62 & 0.618 \\ \end{array}$$ Another example: $$\begin{array}{ccccccccccc} \frac{11}{7} & \frac{18}{7} & \frac{18}{25} & \frac{43}{25} & \frac{43}{68} & \frac{111}{68} & \frac{111}{179} & \frac{290}{179} & \frac{290}{469} & \frac{759}{469} & \frac{759}{1228} \\ 1.57143 & 2.57 & 0.720 & 1.72 & 0.632 & 1.63 & 0.620 & 1.62 & 0.618 & 1.62 & 0.618 \\ \end{array}$$

Q. Why?

• Look at the Möbius transformation $z \mapsto \frac{z+1}{z+2}$. What are its fixed points, two-cycles … – Daniel Fischer Nov 18 '19 at 12:54
• Note: $\phi=\dfrac ab=\dfrac{a+b}{a+2b}\implies \phi=\dfrac{\phi+1}{\phi+2}\implies\phi(\phi+2)=\phi^2+2\phi=\phi+1\implies\phi^2+\phi-1=0$ – J. W. Tanner Nov 18 '19 at 13:39
• Isn't this what makes it golden? – Strawberry Nov 19 '19 at 9:40
• Hint : Compare the iteration's first step to the definition of the golden ratio, and the iterative process to that of the Fibonacci numbers. – Lucian Nov 20 '19 at 8:45

Instead of representing $$\frac{a}{b}$$ as a fraction, represent it as the vector $$\left( \begin{array}{c} a \\ b \end{array} \right)$$.

Then, all you are doing to generate your sequence is repeatedly multiplying by the matrix $$\left( \begin{array}{cc} 1 & 1 \\ 1 & 2 \end{array} \right)$$. One of the eigenvectors of this matrix is $$\left( \begin{array}{c} \frac{\sqrt{5}-1}{2} \\ 1 \end{array} \right)$$, which has a slope equal to the "golden ratio".

This is a standard example of a linear discrete dynamical system, and asymptotic convergence to an eigenvector is one of the typical things that can happen. You can also guess at the long-term behavior of the system by looking at its vector field.

https://kevinmehall.net/p/equationexplorer/#%5B-100,100,-100,100%5D&v%7C(x+y)i+(x+2y)j%7C0.1

In this case you see everything that starts in the first quadrant diverges to infinity along the path of the eigenvector I mentioned before. For your sequence, you started at $$\left( \begin{array}{c} 2 \\ 5 \end{array} \right)$$, which lies in the first quadrant.

Side note: There is nothing particularly special about the golden ratio, the matrix above, or the starting point of $$\left( \begin{array}{c} 2 \\ 5 \end{array} \right)$$ for this sequence. You can change the starting point to be in the negative quadrant if you want to diverge in the opposite direction, and you can change the matrix if you want to diverge along a differently sloped eigenvector.

• @JosephO'Rourke Related: power iteration. Compare this answer. – Kamil Maciorowski Nov 19 '19 at 6:30
• @JosephO'Rourke: This is a good example of how separating the operation iteration from the initial value is valuable. In fact, this viewpoint can motivate matrices! See this explanation for more details. – user21820 Nov 19 '19 at 7:43
• Is the silver ratio (and other ratios in the family) also given by a simple matrix multiplication? – curiousdannii Nov 20 '19 at 23:14
• @curiousdannii The Pell numbers (silver ratio) use the matrix [0 1;1 2]. The Fibonacci numbers (golden ratio) use [0 1;1 1]. Any linear recurrence relation can be expressed in this way. – Brady Gilg Nov 20 '19 at 23:29
• @curiousdannii Because the OP's sequence uses that matrix. It just happens to share an eigenvector with the Fibonacci matrix. – Brady Gilg Nov 20 '19 at 23:37

Let $$f$$ be the map that takes $$a/b$$ to $$(a+b)/(a+2b)$$. We can prove inductively that the $$n$$th iteration of this process gives $$f^n(a/b) = \frac{F_{n}a + F_{n+1}b}{F_{n+1}a + F_{n+2}b},$$ where $$F_n$$ is the $$n$$th Fibonacci number. Since $$b$$ is always non-zero, asymptotically, this ratio approaches $$\lim_{n\rightarrow \infty} \frac{F_{n}a + F_{n+1}b}{F_{n+1}a + F_{n+2}b} = \lim_{n\rightarrow \infty}\frac{F_{n+1}}{F_{n+2}} = \varphi^{-1},$$ by Binet's formula. The argument for the odd convergents is basically identical.

Edit: As M. Winter points out in the comments, the last limit is a little tricky. You can follow the steps outlined in the comments, or here is an alternative. Given fractions $$a/c < b/d$$, the mediant satisfies the inequality $$\frac{a}{c} < \frac{a+b}{c+d} < \frac{b}{d}.$$ In our case, we have $$\frac{F_na}{F_{n+1}a} < \frac{F_na + F_{n+1}b}{F_{n+1}a+F_{n+2}b} < \frac{F_{n+1}b}{F_{n+2}b},$$ so the result follows by the squeeze theorem.

• I am not sure how the rearrangement in you last formula works out (it is not like e.g. $F_{n+1}$ dominates $F_n$), but here is how I would do it: $$\frac{F_{n}a + F_{n+1}b}{F_{n+1}a + F_{n+2}b} = \frac{a + F_{n+1}/F_n \cdot b}{F_{n+1}/F_n\cdot a + F_{n+2}/F_n\cdot b} \to \frac{a+\phi b}{\phi a + \phi^2b} = \frac{a+\phi b}{\phi (a+\phi b)} = \phi^{-1}.$$ – M. Winter Nov 18 '19 at 21:50
• @M.Winter Yes, you are of course correct. Thank you for the correction. – EuYu Nov 18 '19 at 22:35
• Nice to see the Fibonacci connection! – Joseph O'Rourke Nov 19 '19 at 1:39

Your numerators and denominators follow the same recursive relationship that defines the Fibonacci sequence. I.e. each time you make a new number (either a new numerator or a new denominator), the new number is equal to the sum of the two most recent previously made numbers.

Any sequence that follows this recursive relationship (the Fibonacci sequence being the most famous) has, as general term, $$x\cdot \varphi^n + y\cdot (1-\varphi)^n$$ where the exact values of $$x$$ and $$y$$ are decided by what the first two numbers are.

Now note that $$1-\varphi$$ is a number between $$-1$$ and $$0$$, so $$(1-\varphi)^n$$ becomes really small as $$n$$ grows. Which is to say, your two numbers come closer and closer to being pure powerss of the golden ratio. And since they are (close to being) pure powers of the golden ratio, with exponents one apart, the ratio between them is (close to being) the golden ratio. This conclusion is valid for any starting point that doesn't give $$x = 0$$, which apart from starting at $$\frac 00$$ is impossible to do with integers.

First consider the sequence of every second fraction: $$\frac{a_{2n+2}}{b_{2n+2}} = \frac{a_{2n}+b_{2n}}{a_{2n}+2b_{2n}} = \frac{\frac{a_{2n}}{b_{2n}} +1}{\frac{a_{2n}}{b_{2n}} + 2} = f(\frac{a_{2n}}{b_{2n}})$$ where $$f(x)$$ is defined as $$f(x) = \frac{x+1}{x+2} = 1 - \frac{1}{x+2}$$ for $$x \ge 0$$.

Use the monotony of $$f$$ to show that $$\left(\frac{a_{2n}}{b_{2n}}\right)_n$$ is a monotonic and bounded sequence, and determine its limit $$L$$ as the (unique positive) fixed point of $$f$$.

Then consider the fractions with odd indices: $$\frac{a_{2n}}{b_{2n}} \to L$$ implies $$\frac{a_{2n+1}}{b_{2n+1}} = \frac{a_{2n} + b_{2n}}{b_{2n}} \to L + 1 \, .$$

You are re-stating the Fibonacci sequence, and by the theory of linear recurrences, the terms are quasi-proportional to the powers of the largest root of the characteristic equation

$$\phi^2-\phi-1=0.$$

Hence, the ratio of successive terms quickly tends to $$\phi$$.