For an introduction to this series see this article. Essentially, I show examples of beautiful math that are accessible to people with limited math education.
The Fibonacci numbers
The Fibonacci sequence starts with two 1’s, then each subsequent number is the sum of the previous two. The sequence starts:
- 1, 1, 2, 3, 5, 8 ….
The problem
I got this problem from James Tanton’s twitter feed (@JamesTanton). He tweets lots of interesting math problems. Here it is, as he tweeted it:
- Is the product of any k consecutive Fibonacci numbers always a multiple of the product of the first k Fibonacci numbers?
Before reading on, I urge you (very strongly!) to play around. Mathematics is all about play.
My approach to a proof
I have not come up with what I would consider a full, formal proof. But I think I am well on the way. It will be much easier to write about if you know about modular notations. Essentially, modular notation gives remainders from division. For instance 3 mod 2 is the remainder when 3 is divided by 2; that is, 1.
Sometimes when you see a problem, a path to a proof leaps out at you. But this didn’t happen in this case, at least not for me. So, I played. I tried multiplying the first few Fibonacci numbers, then seeing what I got. The first two are easy: 1*1 = 1, and every number is a product of 1. 1*1*2 = 2. Every even number is a product of 2 (by definition). Any three numbers in the Fibonacci sequence can be represented by a, b and a + b, Now, if either a or b is even, then the product of these three numbers must be even. But if both a and b are odd, then a + b must be even and, again, the product must be even. After that, it got a little trickier. However, I took the next step:
Let’s look at 4 terms: 1*1*2*3 = 6. Any four terms of the Fibonacci sequence are representable as a, b, a + b and a + 2b. Since any three terms are divisible by 2 (see above) all we need show is that the product of four terms is divisible by 3 (because if a number is divisible by 2 and by 3, it must be divisible by 6). In modular terms there are these possibilities:
- a mod 3 or b mod 3 = 0; that is, one of the two is divisible by 3. In that case the product of all 4 terms must be divisible by 3.
- a mod 3 = 1 and b mod 3 = 1. In this case, (a + 2b) is divisible by 3.
- a mod 3 = 2 and b mod 3 = 2. In this case (a + 2b) is divisible by 3.
- a mod 3 = 1 and b mod 3 = 2, or vice versa. In this case (a + b) is divisible by 3.
Next, I looked at 5 terms: 1*1*2*3*5 and the product of a, b, (a + b), (a + 2b) and (2a + 3b) and I noticed that the same thing happens, mod 5, as happened mod 3. And, although I haven’t proven it, it seems that the same thing happens with a sequence of any length.
A formalization of this proof might be by mathematical induction, but I haven’t worked it out completely.