## Golden powers

So, we know from a previous challenge that $\varphi^2 = \varphi + 1$. That’s a pretty interesting property, which is shared only by its cousin, $\hat{\varphi}$. I wonder whether other powers of $\varphi$ have special properties too? Let’s see: $\varphi^3 = \varphi \cdot \varphi^2 = \varphi (\varphi + 1) = \varphi^2 + \varphi = 2\varphi + 1.$

Interesting! What about $\varphi^4$? $\varphi^4 = \varphi \cdot \varphi^3 = \varphi (2\varphi + 1) = 2 \varphi^2 + \varphi = 3\varphi + 2.$

And $\varphi^5$? $\varphi^5 = \varphi \cdot \varphi^4 = \varphi (3\varphi + 2) = 3 \varphi^2 + 2\varphi = 5\varphi + 3.$

Curiouser and curiouser! Are you noticing a pattern? (Try working out $\varphi^6$ to see if it fits the pattern you suspect.)

Hopefully, you noticed that Fibonacci numbers are involved here. If this pattern holds, we would expect to find that $\varphi^6 = 8\varphi + 5$, $\varphi^7 = 13\varphi + 8$, and so on. To state it more generally, we suspect that $\varphi^n = F_n \varphi + F_{n-1}$, when $n \geq 2$.

Is this true? It turns out, amazingly, that it is, and we can prove it using a technique called mathematical induction. The idea of mathematical induction is sort of like knocking over a chain of dominoes. First, we’ll show that the above statement is true for some particular value of n (the base case; for this statement, we’ll use n = 2). Then, we’ll show that if the statement is true for any given value of n, then it must be true for n + 1 as well (the inductive step). Do you see how it’s like knocking over dominoes? If the statement is true when n is 2, then it must be true for 3 as well, which means it must be true for 4, which means… and so on, for all positive integers!

Ready? First, recall that the Fibonacci numbers $F_n$ are defined as follows: $\begin{array}{rcl} F_1 = F_2 & = & 1 \\ F_n &= & F_{n-1} + F_{n-2} \qquad (n > 2). \end{array}$

Now for the base case: when n is 2, the statement says that $\varphi^2 = F_2 \varphi + F_1$; this is true since $F_2$ and $F_1$ are both equal to 1.

Finally, the inductive step. We’ll begin by supposing that $\varphi^n = F_n \varphi + F_{n-1}$ for some $n \geq 2$, and see if this allows us to conclude that the statement is true for $n + 1$ as well. The method we used above to evaluate $\varphi^3$, $\varphi^4$ and so on suggests a method of attack: $\begin{array}{rcl} \varphi^{n+1} &=& \varphi \cdot \varphi^n \\ &=& \varphi \cdot (F_n \varphi + F_{n-1}) \\ &=& F_n \varphi^2 + F_{n-1} \varphi \\ &=& F_n (\varphi + 1) + F_{n-1} \varphi \\ &=& (F_n + F_{n-1}) \varphi + F_n \\ &=& F_{n+1} \varphi + F_n \end{array}$

So, since we’ve proved that the statement is true when n is 2, and we’ve also proved that it must be true for n + 1 whenever it’s true for n, it must be true for all $n \geq 2$!

Next up: we’ll use this neat relationship between $\varphi$ and the Fibonacci numbers to discover another one! Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in famous numbers, fibonacci, golden ratio, induction, proof. Bookmark the permalink.

### 6 Responses to Golden powers

1. Jonathan says:

Nice one! I didn’t know this.

2. Pingback: Carnival of Math #18 « JD2718

3. polymath says:

Nice proof. The first equality you state (used for the cousin, not phi itself) is used prominently in the proof on my blog at http://polymathematics.typepad.com/polymath/trekking-into-the-desert.html

It’s a great example of how phi shows up in the oddest places.

4. George Bell says:

The formula also works for negative powers (n) if you define F_{-n}=(-1)^{n+1}F_n. Rather amazing!

I have used this formula on several recent papers on peg solitaire, for example

http://arxiv.org/abs/math.CO/0612612

5. Brent says:

Indeed!