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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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 \, . $$

Answer 5

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$.