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