Patrick Snow of Dame Alice Owens School, London, Marcos Charalambides from Cyprus and Andrei Lazanu from Romania sent solutions to this problem.

The famous golden ratio is $g = \frac{\sqrt{5} + 1}{2}$ . Patrick and Andrei showed that

$g^{2} = \frac{(\sqrt{5} + 1)^{2}}{4} = \frac{(6 + 2 \sqrt{5})}{4} = \frac{(\sqrt{5} + 3)}{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 = \frac{1 \pm \sqrt{5}}{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$

$\begin{matrix} g^{2} & = g + 1 \\ g^{3} & = g^{2} + g = 2 g + 1 \\ g^{4} & = 2 g^{2} + g = 3 g + 2 \\ g^{5} & = 3 g^{2} + 2 g = 5 g + 3 \\ g^{6} & = 5 g^{2} + 3 g = 8 g + 5 \\ \dots \end{matrix} .$

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_{n} g + b_{n}$ as follows. Multiplying by $g$ gives

$g^{n + 1} = a_{n} g^{2} + b_{n} g = a_{n} (g + 1) + b_{n} g = (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_{n} g + 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} = \frac{α^{n} - β^{n}}{\sqrt{5}}$ where $α$ and $β$ are the solutions of the quadratic equation $x^{2} = x + 1$ . Now for $n = 1$

$α - β = \frac{1 + \sqrt{5}}{2} - \frac{1 - \sqrt{5}}{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$

$\frac{α^{2} - β^{2}}{\sqrt{5}} = \frac{(α + 1) - (β + 1)}{\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 $α^{2} = α + 1$ and $β^{2} = β + 1$ then

$\begin{matrix} a_{k + 1} & = a_{k} + a_{k - 1} \\ = \frac{α^{k - 1} (α + 1) - β^{k - 1} (β + 1)}{\sqrt{5}} \\ = \frac{α^{k + 1} - β^{k + 1}}{\sqrt{5}} \end{matrix}$

Hence by the axiom of induction the result is proved. Thus

$g^{n} = \frac{α^{n} - β^{n}}{\sqrt{5}} g + \frac{α^{n - 1} - β^{n - 1}}{\sqrt{5}} .$