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.
Yay, Bahamas! Yay, Flags of Many Lands™!
Now playing: William Bell - Just as I Thought