Copyright © University of Cambridge. All rights reserved.
'Golden Powers' printed from https://nrich.maths.org/
Patrick of Dame Alice Owens School, London, Marcos from Cyprus and
Andrei from Romania sent solutions to this problem.
The famous golden ratio is $g={\sqrt5 + 1 \over 2}$. Patrick and
Andrei showed that $$g^2 = {(\sqrt5 + 1 )^2\over 4} = {(6 + 2\sqrt
5) \over 4} = {(\sqrt 5 + 3)\over 2} = g + 1$$.
Marcos considered the equation $x^2 = x + 1$. By completing the
square, $$(x - 1/2)^2 = 5/4$$ he obtained the solutions $$x={1 \pm
\sqrt5 \over 2}.$$ So $g$ is one solution of this equation and
hence $g^2=g+1$.
Both Andrei and Marcos then experimented a bit to get familiar with
the problem...
Multiplying by $g$
$$\eqalign{ g^2 &= g+1 \cr g^3 &= g^2 + g = 2g + 1 \cr g^4
&= 2g^2 + g = 3g + 2 \cr g^5 &= 3g^2 + 2g = 5g + 3 \cr g^6
&= 5g^2 + 3g = 8g + 5 \cr \cdots }.$$
Marcos then made the conjecture that $a_{n+1} = a_n + a_{n-1}$ and
these coefficients are the Fibonacci sequence. Similarly for the
$b_n$ and went on to prove this conjecture using the method of
mathematical induction.
Patrick used the result $g^2=g+1$ to find a pattern in the
coefficients for $g^n = a_ng + b_n$ as follows. Multiplying by $g$
gives
$$g^{n+1}= a_ng^2 + b_ng = a_n(g+1) + b_ng = (a_n+b_n)g + a_n.$$
Thus $a_{n+1}=a_n+b_n$ and $b_{n+1}=a_n$. Hence $a_{n+1}=a_n +
a_{n-1}$. This is the Fibonacci sequence. Since the first terms are
$a_1=1$ and $a_2=1$ so $g^n=a_ng+a_{n-1}$ where $a_k$ is the $k$-th
term of the Fibonacci sequence.
Then Patrick went on to prove by induction that $a_n={{\alpha
^n-\beta ^n}\over \sqrt 5}$ where $\alpha$ and $\beta$ are the
solutions of the quadratic equation $x^2 = x + 1$. Now for $n=1$
$$ \alpha - \beta = {{1+\sqrt 5}\over 2} - {{1-\sqrt 5}\over
2}=\sqrt 5 $$
and dividing this by $\sqrt 5$ gives the value of $a_1=1$ showing
that the result is true for $n=1$. For $n=2$
$${{\alpha ^2 - \beta^2}\over \sqrt 5} = {{(\alpha + 1)- (\beta
+1)}\over \sqrt 5} = 1$$
as above giving the value of $a_2=1$ showing that the result is
true for $n=2$. Assume the result for $n=k$ and $n=k-1$ and using
the fact that $\alpha^2 = \alpha +1$ and $\beta^2=\beta +1$ then
$$\eqalign{ a_{k+1} &= a_k + a_{k-1} \cr &=
{{\alpha^{k-1}(\alpha+1)-\beta^{k-1}(\beta+1) }\over \sqrt 5} \cr
&= {{\alpha^{k+1}-\beta^{k+1}\over \sqrt 5}}}$$
Hence by the axiom of induction the result is proved. Thus
$$ g^n = {{\alpha^n-\beta^n}\over \sqrt 5}g + {{\alpha^{n-1} -
\beta^{n-1}}\over \sqrt 5}.$$