If I start writing down the numbers
1, 1, 2, 3, 5, 8, 13, 21 ...
you will probably instantly recognize them as Fibonacci numbers. A quick reminder, adding any two adjacent numbers generates the next Fibonacci number. So since 1+1 =2 we get that 2 is Fibonacci number, then 1+2=3 so we get that 3 is a Fibonacci numbers.
You probably already read about the connection between the Fibonacci numbers and the golden ratio. However, there are plenty more interesting properties. Today we will look at a `Mathemagical' statement which you can use to read someone's mind :o)
Mathemagic of Fibonacci numbers
Let me start with the `Magical' statement:
Mathemagical statement Take any two different Fibonacci numbers (they do not have to be adjacent Fibonacci numbers) and then add them together. Let's call this number X. Suppose you would only tell me X then without knowing which Fibonacci numbers you chose I can determine the Fibonacci numbers you used to get X.
To convince you a bit let's first show this with an example. So suppose you are only allowed to use Fibonacci numbers les or equal to 5. Then let's look at all the possibilities
1+1=2
1+2=3
1+3=4
2+3=5
1+5=6
2+5=7
3+5=8
You see that for any any whole number between 1 and 9 there is a unique pair of Fibonacci numbers. You might then think that the following is true: any number greater than one can be written as a unique combination of two different Fibonacci numbers. But this is not true. For example, 12 cannot be expressed as the sum of two Fibonacci numbers.
Proof by contradiction
So how do we go about proving this Mathemagical statement. We will prove the Mathemagical statement by using proof by contradiction. This means that will assume that the contrary of the Mathemagical statement is true and then show that this implies that something which we know should be true is not true. Let us clarify this with an example: suppose you want to prove that a needle is sharp. Then if you would apply a proof by contradiction you would assume that it is not sharp. So if the needle is not sharp then if I use it to poke my finger then no blood should come out. However, when I used it to poke my finger a fair amount of blood came out. So the initial assumption that the needle is not sharp is incorrect and we conclude that the needle is sharp.
Proof of the Mathemagical statement
So how do we formulate the contrary of the Mathemagical statement? In this setting the contrary means that the sum of two Fibonacci numbers can be expressend in two (or more) ways. So there exist four different Fibonacci numbers which we will denote by 
such that
One of these Fibonacci numbers has to be the biggest. Without los of generality we can assume that 
is bigger than the Fibonacci numbers 
. We now need to introduce some notation. We will denote the nth Fibonacci number by 
. Recalling how Fibonacci numbers are generated we have for 
that
We know that that there must exists a k such that 
. Since all Fibonacci numbers are positive we then get
Since is the largest Fibonacci numbers and since 
are different Fibonacci numbers we know that
Using (2) we get that
Inserting the inequalities (3) and (4) in the equality (1) we get that
Just to make it a bit clearer let 
. Then we get that
This cannot be true! So have completed the contradiction and in doing so shown the Mathemagical statement.
The little fibs card trick and the Mathemagical statement
Source
This Mathemagical statement has actually been implemented in a card trick, called the little fibs trick.
The magicians shuffles a deck and presents you with a pile of cards. You then selects two cards. The magician then asks you to add the values of these cards. The values are determines as followd: ace=1, 2=2, 3=3, ..., 10=10, jack=11, queen=12 and king =13 (suits have no value). When you tell the magician the value of the sum the magician can tell you which cards you selected.
So how does this trick work? The non-mathematical part is that the magician shuffled the deck in such a way that you could only select from a pile of cards which correspond to Fibonacci numbers. From there on it is just mathematics. So the name of this trick has a double meaning since little fibs means little lie but it also is a short notation for little fibonacci numbers where little means low.
Here is a numberphile video showing/explaining the procedure in detail and a bit of the maths.
Zeckendorf's theorem
Our Mathemagical statement gives rise to the question under what conditions can any positive whole number be represented as the sum of Fibonacci numbers. The Zeckendorf's theorem answers this question. It states that every positive whole number can be uniquely represented as a Fibonacci number or as the sum of different Fibonacci numbers which do not include consecutive Fibonacci numbers. So we have the following informal statement
in a very specific sense the Fibonacci numbers form the unique building blocks of the whole numbers.
Sources
This is a bit based on the numberphile video about the little fibs magic trick. The proof does not appear in this video. However, somebody put a proof in the comments section of the numberphile video. That proof uses a mathematical technique called induction. This is not necessary. So I think my proof is shorter and easier.
Equations made using quicklatex. It is free to use.
Top picture: Marvelous feats in mind reading, Litography, U.S. Printing Co., Russell-Morgan Print (1900), Cincinnati & New York
Further reading
For a proof of the Zeckdorf theorem you can check this wiki page.
Thank you!
Thanks for being so kind to read my post. You are awesome! Please follow me if you enjoyed it. If you have any questions just post them below and I will answer them. Or if you might have a nice topic you want me to cover also let me know below. In my next post I think I will write about continuous functions. :o)
Owl tax
A few months ago, I visited London. I found this amazing taxidermy of a Tawny owl in the British Natural History museum.