Wednesday, January 30, 2008

Wednesday Math, Vol. 13: A quick proof

I had an idea for a "quick" post today about the Fibonacci numbers and their mutant cousins the Lucas numbers.

We did the Fibonacci numbers a few weeks back. You start with 1 and 1 as the first two numbers, and the next Fibonacci is the last two added up. The Lucas numbers are like the Fibonaccis, but the sequence starts with 2 and 1. Here the first few numbers on both infinitely long lists.

Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...
Lucas sequence: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, ...

Notice that 1, 2 and 3 are on both lists, which means that 3, for example, is both a Fibonacci number and a Lucas number. After that the lists diverge, and none of the numbers bigger than 3 show up on both lists, at least as far as I've written. It turns out that 3 is the largest number that is both a Fibonacci number and a Lucas number.

Statement: 3 is the largest number that is both a Fibonacci number and a Lucas number.

Proof:
Let's give position numbers to both lists, written as subscripts.

F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5, F6 = 8, F7 = 13,...

L1 = 2, L2 = 1, L3 = 3, L4 = 4, L5 = 7, L6 = 11, L7 = 18,...

While we can get the next Lucas number by adding the last two on the list together, we can also get it by adding up a Fibonacci number and the Fibonacci two back on the list. This is what I mean, starting with the Lucas number 4 and the Fibonacci numbers 3 and 1.

4 = 3+1
7 = 5+2
11 = 8+3
18 = 13+5...

Using our numbering system and
n to represent any position in the list, we get this equation

Ln = Fn + Fn-2

Using this same numbering system, we have the formula for the next Fibonacci number.

Fn+1 = Fn + Fn-1

Because every Fibonacci number is bigger than the last once we get past the two copies of the number 1 at the beginning of the list, what this means is

Fn < Ln < Fn+1

If I merged the two lists, once we get past 3, the list would go Lucas (4), Fibonacci (5), Lucas (7), Fibonacci (8), Lucas (11), Fibonacci (13), etc., interleaved infinitely. So nothing on the Lucas list can equal anything on the Fibonacci list once we get past 3.

Q.E.D. which is Latin for Quick Explanation, Dude!

Okay, no it isn't really. But the proof is true.

Make sense?


Yay, Bahamas! Yay, Flags of Many Lands™!



----------------
Now playing: William Bell - Just as I Thought
via FoxyTunes

5 comments:

dguzman said...

I'd never heard of the Lucas numbers, only Fibonacci. Lucas must be kinda bummed that his numbers aren't as popular.

Matty Boy said...

When I called Lucas a mutant variation, there was more truth in that than just snark. If a cell growth pattern starts with some double cell that doesn't split properly at the first step, the resulting organism may have a Lucas number of appendages instead of a Fibonacci number. It was used to explain to me why three leaf clover are common and four leaf clover are rare.

FranIAm said...

Oh I so totally got that!

My head hurts.

Matty Boy said...

Fran, if it hurts, you're not doing it right.

Distributorcap said...

quod erat demonstrandum