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 ?
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!