Golden powers
You add 1 to the golden ratio to get its square. How do you find higher powers?
Age
16 to 18
Challenge level
Problem
The famous golden ratio is $g={\sqrt5 + 1 \over 2}$. Prove that $g^2=g+1$.
Let $g^n = a_ng + b_n$. Find the sequences of coefficients $a_n$ and $b_n$.
Getting Started
You will probably need to experiment a little to try to form a conjecture for the form of the coefficients. You can then use induction to try to prove your conjecture.
Student Solutions
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}.$$
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}.$$