Golden Powers

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