Finding Patterns in the Fibonacci Sequence

This is the final post (at least for now) in a series on the Fibonacci numbers. We’ve gone through a proof of how to find an exact formula for all Fibonacci numbers, and how to find exact formulas for sequences of numbers that have a similar definition to the Fibonacci numbers. But, the fact that the Fibonacci numbers have a surprising exact formula that arises from quadratic equations is by no stretch of the imagination the only interesting thing about these numbers. In fact, there is an entire mathematical journal called the Fibonacci Quarterly dedicated to publishing new research about the Fibonacci sequence and related pieces of mathematics [1]. In fact, a few of the papers that I myself have been working on in my own research use facts about what are called Lucas sequences (of which the Fibonacci sequence is the simplest example) as a primary object (see [2] and [3]).

The goal of this article is to discuss a variety of interesting properties related to Fibonacci numbers that bear no (direct) relation to the exact formula we previously discussed.

New Recurrence Relations

In this series, we have made frequent mention of the fact that the fraction \dfrac{F_{n+1}}{F_n} is very close to the golden ratio \varphi. We can now extend this idea into a new interesting formula. Since this is the case no matter what value of n we choose, it should be true that the two fractions \dfrac{F_{n+1}}{F_n} and \dfrac{F_n}{F_{n-1}} are very nearly the same. Therefore,

\dfrac{F_{n+1}}{F_n} \approx \dfrac{F_n}{F_{n-1}} \implies F_{n+1}F_{n-1} \approx F_n^2 \implies F_{n+1} F_{n-1} - F_n^2 \approx 0.

One question we could ask, then, is what we actually mean by approximately zero. Is this ever actually equal to 0? What is the actual value? Let’s look at a few examples. Remember, the list of Fibonacci numbers starts with 1, 1, 2, 3, 5, 8, 13. Let’s look at three strings of 3 of these numbers: 2, 3, 5; 3, 5, 8; and 5, 8, 13. The expression F_{n+1} F_{n-1} - F_n^2 mandates that we multiply the largest by the smallest, multiply the middle value by itself, and then subtract the two. So, we get:

(5)(2) - 3^2 = 10 - 9 = 1,

(8)(3) - 5^2 = 24 - 25 = -1,

(13)(5) - 8^2 = 65 - 64 = 1.

Well, that certainly appears to look like some kind of pattern. It looks like we are alternating between 1 and -1. And as it turns out, this continues. The proof of this statement is actually quite short, and so I’ll prove it here.

Theorem: For every whole number n \geq 1, the equation

F_{n+1} F_{n-1} - F_n^2 = (-1)^n

is always true.

Proof: This proof uses the method of mathematical induction (see my article [4] to learn how this works). We first must prove the base case, n = 1. When n = 1, we know that F_{n-1} = F_0 = 0, F_n = F_1 = 1, and F_{n+1} = F_2 = 1. Therefore, F_{n+1} F_{n-1} - F_n^2 = (1)(0) - 1^2 = -1 = (-1)^1. Therefore, the base case is established.

Now, we assume that we have already proved that our formula is true up to a particular value of n. We want to prove that it is then true for the value n+1. That is, we need to prove using the fact that F_{n+1} F_{n-1} - F_n^2 = (-1)^n to prove that F_{n+2} F_n - F_{n+1}^2 = (-1)^{n+1}. To do this, first we must remember that by definition, F_{n+2} = F_{n+1} + F_n. Using this, we can conclude (by substitution, and then simplification) that

F_{n+2} F_n - F_{n+1}^2 = (F_{n+1} + F_n) F_n - F_{n+1}^2 = F_n F_{n+1} + F_n^2 - F_{n+1}^2 = F_n F_{n+1} + (F_n - F_{n+1})(F_n + F_{n+1}).

Now, recall that F_{n+1} = F_n + F_{n-1}, and therefore that F_n - F_{n+1} = - F_{n-1} and F_{n+1} - F_{n-1} = F_n. Therefore, extending the previous equation,

F_{n+2} F_n - F_{n+1}^2 = F_n F_{n+1} - F_{n-1}(F_n + F_{n+1}) = F_n F_{n+1} - F_{n-1}F_n - F_{n-1}F_{n+1}

= F_n(F_{n+1} - F_{n-1}) - F_{n-1}F_{n+1} = F_n^2 - F_{n-1}F_{n+1}.

Since we originally assumed that F_{n+1} F_{n-1} - F_n^2 = (-1)^n, we can multiply both sides of this by -1 and see that F_n^2 - F_{n-1} F_{n+1} = (-1)(-1)^n = (-1)^{n+1}. This is exactly what we just found to be equal to F_{n+2} F_n - F_{n+1}^2, and therefore our proof is complete.

The Pisano Period

The first four things we learn about when we learn mathematics are addition, subtraction, multiplication, and division. These are all tightly interrelated, of course, but it is often interesting to look at each individually or in pairs. Here, we will do one of these pair-comparisons with the Fibonacci numbers. The most important defining equation for the Fibonacci numbers is F_{n+1} = F_n + F_{n-1}, which is tightly addition-based. In light of the fact that we are originally taught to do multiplication by “doing addition over and over again” (like the fact that 2 \times 3 = 2 + 2 + 2 = 3 + 3), it would make sense to ask whether the addition built into the Fibonacci numbers has any implications that only show up once we start asking about multiplication. The answer here is yes.

The multiplicative pattern I will be discussing is called the Pisano period, and also relates to division. In order to explain what I mean, I have to talk some about division. When we learn about division, we often discuss the ideas of quotient and remainder. In case these words are unfamiliar, let me give an example. Imagine that you have some people that you want to split into teams of an equal size. You are, in this case, dividing the number of people by the size of each team. The number of teams you are able to make is called the quotient, and if you have people left over that can’t fit into these teams, that number is called the remainder. For example, if you have 23 people and you want to make teams of 5, then you will make 4 teams and there will be 3 people left out – which means that 23/5 has a quotient of 4 and a remainder of 3.

Remainders actually turn out to be extremely interesting for a lot of reasons, but here we primarily care about one particular reason. A remainder is going to be a zero exactly whenever everybody gets to be a part of a team and nobody gets left over. In terms of numbers, if you divide a number N by a (smaller) number M, then the remainder will be zero if N is actually a multiple of M – so N is something like 2N, 3N, 4N, 5N, etc. As it turns out, remainders turn out to be very convenient way when dealing with addition. This is because if you have any two numbers, the idea of computing remainders and adding the numbers together can be done in either order. For example, recall the following rules for even/odd numbers:

Even + Even = Even

Even + Odd = Odd

Odd + Even = Odd

Odd + Odd = Even.

Since even/odd actually has to do with remainders when you divide by 2, we can express these in terms of remainders. A number is even if it has a remainder of 0 when divided by 2, and odd if it has a remainder of 1 when divided by 2. In these terms, we can rewrite all of the above equations:

Even + Even = Remainder 0 + Remainder 0 = Remainder (0+0) = Remainder 0 = Even,

Even + Odd = Remainder 0 + Remainder 1 = Remainder (0+1) = Remainder 1 = Odd,

Odd + Even = Remainder 1 + Remainder 0 = Remainder (1+0) = Remainder 1 = Odd,

Odd + Odd = Remainder 1 + Remainder 1 = Remainder (1+1) = Remainder 2 = Even.

This interplay is not special for remainders when dividing by 2 – something similar works when calculating remainders when dividing by any number. This now enables me to phrase the interesting result that I want to communicate about Fibonacci numbers:

Theorem: Let N be a positive whole number. Then if we compute the remainders of the Fibonacci numbers upon dividing by N, the result is a repeating pattern of numbers. As a consequence, there will always be a Fibonacci number that is a whole-number multiple of N.

Proof: What we must do here is notice what happens to the defining Fibonacci equation F_{n+1} = F_n + F_{n-1} when you move into the world of remainders. With regular addition, if you have some equation like a + b = c, if you know any two out of the three numbers a,b,c, then you can find the third. The same thing works for remainders – if you know two of the remainders of a,b,c when divided by N, then there is a straightforward way you can find the third remainder (this is the sort of thing we just did with odd/even). Now, here is the important observation. If you are dividng by N, the only possible remainders of any number are 0, 1, 2, \dots, N-1. There are N possible remainders. This exact number doesn’t matter so much, what really matters is that this number is finite.

When we combine the two observations – that if you know the remainders of both F_{n-1} and F_n when divided by N, and you know the remainder of F_{n+1} when divided by N and that there are only a finite number of ways that you can assign remainders to F_{n-1} and F_n, you will eventually come upon two pairs (F_{m-1}, F_m) and $(F_{n-1}, F_n)$ that will have the same remainders. Since this pair of remainders is enough to tell us the remainder of the next term, F_{m+1} and F_{n+1} have the same remainder. This always holds, and so you arrive at a forever-repeating pattern. Because the very first term is F_0 = 0, which has a remainder of 0, and since the pattern repeats forever, you eventually must find another remainder of 0. This fully explains everything claimed.

References

[1] See https://fq.math.ca/ for the Fibonacci Quarterly journal.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: