# Solution

Suppose $\varphi$ denotes the golden ratio and $\phi$ denotes its negative reciprical. Find the first few powers of each. What can you say about their differences, $\varphi^n - \phi^n$? Make a conjecture and prove it with induction.

Recall, the golden ratio is given by

$$\varphi = \frac{1+\sqrt{5}}{2}$$

First, we need to find the value of $\phi$, the negative reciprical of the golden ratio, $\phi$,

$$\begin{array}{rcl} \phi &=& -\frac{2}{1+\sqrt{5}}\\\\ &=& -\frac{2}{1+\sqrt{5}} \cdot \frac{1-\sqrt{5}}{1-\sqrt{5}}\\\\ &=& \frac{-2(1-\sqrt{5})}{-4}\\\\ &=& \frac{1-\sqrt{5}}{2} \end{array}$$

Now if we expand and simplify $\varphi^n - \phi^n$ for the first few positive integers $n$, we find:

$$\begin{array}{cccc} \left( \frac{1 + \sqrt{5}}{2} \right)^1 - \left( \frac{1 - \sqrt{5}}{2} \right)^1 & = & \sqrt{5} \\\\ \left( \frac{1 + \sqrt{5}}{2} \right)^2 - \left( \frac{1 - \sqrt{5}}{2} \right)^2 & = & \sqrt{5} \\\\ \left( \frac{1 + \sqrt{5}}{2} \right)^3 - \left( \frac{1 - \sqrt{5}}{2} \right)^3 & = & 2\sqrt{5} \\\\ \left( \frac{1 + \sqrt{5}}{2} \right)^4 - \left( \frac{1 - \sqrt{5}}{2} \right)^4 & = & 3\sqrt{5} \\\\ \left( \frac{1 + \sqrt{5}}{2} \right)^5 - \left( \frac{1 - \sqrt{5}}{2} \right)^5 & = & 5\sqrt{5} \\\\ \left( \frac{1 + \sqrt{5}}{2} \right)^6 - \left( \frac{1 - \sqrt{5}}{2} \right)^6 & = & 8\sqrt{5} \\\\ \left( \frac{1 + \sqrt{5}}{2} \right)^7 - \left( \frac{1 - \sqrt{5}}{2} \right)^7 & = & 13\sqrt{5} \end{array}$$

We conjecture that $\varphi^n -\phi^n = F_n \sqrt{5}$ where $F_n$ is the $n^{th}$ term of the Fibonacci sequence. Recall the terms of the Fibonacci sequence are defined by the recursive relationship $F_n = F_{n-1} + F_{n-2}$ along with $F_0=F_1=1$.)

We argue by strong induction...

The basis step is already well established by the calculations in the list above.

Proceeding with the inductive step, we need to show that if $\varphi^n -\phi^n = F_n \sqrt{5}$ for every $n \le k$, then $\varphi^{k+1} -\phi^{k+1} = F_{k+1} \sqrt{5}$.

Working from the right side to the left, we have

$$\begin{array}{rcl} F_{k+1} \sqrt{5} &=& \sqrt{5} (F_k + F_{k-1})\\\\ &=& \sqrt{5} F_k + \sqrt{5} F_{k-1}\\\\ &=& \sqrt{5} \left( \frac{\varphi^k - \phi^k}{\sqrt{5}} \right) + \sqrt{5} \left( \frac{\varphi^{k-1} - \phi^{k-1}}{\sqrt{5}} \right) \quad \quad \textrm{...by the inductive hypothesis}\\\\ &=& \varphi^k - \phi^k + \varphi^{k-1} - \phi^{k-1}\\\\ &=& (\varphi^k + \varphi^{k-1}) - (\phi^k + \phi^{k-1})\\\\ &=& \varphi^{k-1} (\varphi + 1) - \phi^{k-1} (\phi + 1)\\\\ &=& \varphi^{k-1} \varphi^2 - \phi^{k-1} \phi^2 \quad \quad \textrm{...see note below}\\\\ &=& \varphi^{k+1} - \varphi^{k+1} \end{array}$$

Note: the last two steps may not seem obvious at first blush, but remember we know where we are headed. We know we need to link up the left side and right side below: $$\varphi^{k-1} (\varphi + 1) - \phi^{k-1} (\phi + 1) = \cdots = \varphi^{k+1} - \varphi^{k+1}$$

So it sure would be nice if $\varphi + 1 = \varphi^2$ and $\phi + 1 = \phi^2$. Since we know the exact values of $\varphi$ and $\phi$, we can check to see if this is the case by simple evaluation -- and it is:

$$\left( \frac{1 \pm \sqrt{5}}{2} \right) + 1 = \frac{3 \pm \sqrt{5}}{2}$$

and
$$\left( \frac{1 \pm \sqrt{5}}{2} \right)^2 = \frac{1 + 2\sqrt{5} + 5}{4} = \frac{6 \pm 2\sqrt{5}}{4} = \frac{3 \pm \sqrt{5}}{2}$$

(Alternatively, if you recall that $\varphi$ and $\phi$ are the roots of the quadratic equation $x^2 -x - 1 = 0$, then isolating the $x^2$ on one side reveals the desired relationship immediately.)

This completes the induction step, so by the second principle of mathematical induction (i.e., strong induction), the following holds for all positive integers $n$: $$\varphi^n -\phi^n = F_n \sqrt{5}$$ QED.