So, we know from a previous challenge that . That’s a pretty interesting property, which is shared only by its cousin, . I wonder whether other powers of have special properties too? Let’s see:

Interesting! What about ?

And ?

Curiouser and curiouser! Are you noticing a pattern? (Try working out 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 , , and so on. To state it more generally, we suspect that

, when .

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 are defined as follows:

Now for the base case: when *n* is 2, the statement says that ; this is true since and are both equal to 1.

Finally, the inductive step. We’ll begin by *supposing* that for some , and see if this allows us to conclude that the statement is true for as well. The method we used above to evaluate , and so on suggests a method of attack:

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 !

Next up: we’ll use this neat relationship between and the Fibonacci numbers to discover another one!

Nice one! I didn’t know this.

Pingback: Carnival of Math #18 « JD2718

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.

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

Indeed!

Pingback: Explicit Fibonacci numbers | The Math Less Traveled