While trying to prove that the sequence $a_{n+1}=1+\frac{1}{a_n}$ with $a_1=2$ converges to Phi(the second sequence obviously converges to Phi), I recognized the pattern when I calculated the first couple terms.
I proved it with induction but I can't find any other way to prove the equivalence. Any help is greatly appreciated.
we demand $a_n = \frac{p_n}{q_n}$ with $\gcd(p_n, q_n) = 1$ and $q_n \geq 1$ This is unambiguous, we are writing the fraction in lowest terms.
Next, $$ p_{n+1} = p_n + q_n \; , \; \; \; q_{n+1} = p_n $$ in which we may confirm the new denominator and denominator are coprime.
Finally $$ p_{n+2} = 2 p_n + q_n= p_n + (p_n + q_n) = p_n + p_{n+1} \; . \; \; $$
along with $$ q_{n+2} = p_n + q_n = q_{n+1} + q_n $$
That is the familiar recurrence for Fibonacci or Lucas numbers. One may finish by finding the explicit fractions that show $p_1, p_2, p_3 .$ Apparently $a_1 = 2 = \frac{2}{1}$ and $a_2 = \frac{3}{2}$ and $a_3 = \frac{5}{3}.$
To get the Lucas numbers, begin with $a_1 =3$
Note that the recurrences $ p_{n+2} = p_{n+1} + p_n $ and $ q_{n+2} = q_{n+1} + q_n $are just Cayley Hamilton for
$$ \left( \begin{array}{cc} 1&1 \\ 1&0 \\ \end{array} \right) $$