The Fibonacci sequence is an integer sequence defined by a simple linear recurrence relation. The sequence appears in many settings in mathematics and in other sciences. In particular, the shape of many naturally occurring biological organisms is governed by the Fibonacci sequence and its close relative, the golden ratio.
The Fibonacci numbers are the terms of a sequence of integers in which each term is the sum of the two previous terms with
The first few terms are
Let be the golden ratio. Let Then
The formula (often called Binet's formula) comes from a general result for linear recurrence relations, but it can be proved directly by induction. Let . The goal is to prove that by induction on . The base cases are , which is clear. Now suppose for all , where is at least . Then
where the last line comes from the fact that and are the two roots of the equation .
Note that for , the term is small, certainly between and . So is the nearest integer to .
so and .
The ratios of successive Fibonacci numbers should therefore be roughly
This can be proved easily using Binet's formula.
and the terms and approach as , because the numerator approaches and the denominator approaches .
Therefore, the limit is .
The Fibonacci sequence appears as the numerators and denominators of the convergents to the simple continued fraction
This continued fraction equals since it satisfies (and it is greater than 1).
The convergent to this continued fraction is , so this gives another proof that .
Like the Catalan numbers, the Fibonacci numbers count many types of combinatorial objects. Here are four examples.
(1) is the number of compositions of consisting of s and s. (A composition of is an expression of as a sum of parts, where the order of the parts matters.) For instance,
(2) is the number of ways to tile a board with dominoes.
(3) is the number of binary sequences of length with no consecutive s.
(4) is the number of subsets of that do not contain any pair of consecutive numbers.
To see that the Fibonacci numbers count these objects, let the number of objects equal and show that . Then verify that and , and the proof is complete.
For instance, to prove (4), start with , and then suppose is a subset of without any consecutive numbers in it. There are such sets that don't contain . If contains , then it doesn't contain , so is obtained by taking a subset of and throwing in . So there are such sets . This proves that as desired.
A clown can climb a staircase either by one step or by two steps. For example, he can climb from the floor to the first step and then to the third, or he can climb from the floor to the first step, then to the second, and then finally to the third.
If a staircase has 10 steps, in how many ways can the clown climb it?
- When he climbs from the step to the he has climbed the whole stair; that is, the final step is the second floor.
- The order in which he climbs the staircase matters!
Bonus: Generalize it.
There are quite a few identities relating different Fibonacci numbers. For instance,
which has the useful corollary that consecutive Fibonacci numbers are coprime.
As is typical, the most down-to-earth proof of this identity is via induction. It is clear for , and now suppose that it is true for . Then
so it is true for .
The proofs of the rest of these identities are similar.
Once upon a time, a rabbit and a turtle were competing in a race.
The fast rabbit could hop in an increasing distance similar to the Fibonacci sequence (omitting the first 1-term) as shown above:
The slow turtle could roll in an increasing distance of an arithmetic sequence of 1-interval as shown:
Though seemingly even at the first three steps, soon afterwards, the rabbit rapidly went ahead of his opponent. However, at one point, the rabbit, confident of his victory, stopped for a nap. Later on, the turtle continued his track in the same pattern and met the rabbit at that same distance. The turtle then carried on his effort before eventually winning the race.
According to this tale, what is the least possible distance from the start to the rabbit's sleeping point?
I was cleaning up my attic recently and found a set of at least 14 sticks which a curious Italian gentleman sold me some years ago. Trying hard to figure out why I bought it from him, I realized that the set has the incredible property that there are no sticks that can form a triangle. If the set has two sticks of length , which are the smallest, what is the least possible length of the stick?
The generating function of the Fibonacci numbers is
This follows from the expansion:
The above shows the first few digits (actually 65) of the decimal representation of the fraction If we split the digits into partitions of 5, we can see that the numbers form a Fibonacci sequence: . How many positive Fibonacci numbers can we find before the pattern breaks off?
Note: For example, suppose that the fraction equals instead of the one given at the top. Then you could only find the first five Fibonacci numbers, namely . So your answer would then be that there are 4 positive Fibonacci numbers before the pattern breaks off.
- Bonus: Generalize this.
- Try Daniel Liu's problem that was inspired by this problem.
Identity (1) above can be used to show that if , then . In fact, more is true:
This follows from (1) and a process similar to the Euclidean algorithm; write and then
and so on.
Note that this discussion implies that if is prime, then is prime or . The converse is not true and in fact it is not known whether there are infinitely many primes such that is prime.
A Zeckendorf representation of a positive integer is an expression of the integer as a sum of (at least one) distinct non-consecutive Fibonacci numbers. For instance, is a Zeckendorf representation of .
Every positive integer has exactly one Zeckendorf representation.
To show first that there cannot be more than one representation, use the identities in item (3) above to see that the sum of any non-consecutive Fibonacci numbers of which the largest is cannot be larger than note that and are consecutive Fibonacci numbers since Then suppose that there are two Zeckendorf representations of an integer, and subtract out all the common Fibonacci numbers in the two sums. Then the resulting two sums are still equal, and consist of two disjointed sets of Fibonacci numbers. Suppose the largest Fibonacci number in the first sum is and the largest Fibonacci number in the second sum is ; suppose without loss of generality that . Then the first sum is less than but the second sum is clearly , so they cannot be equal.
To see that a Zeckendorf representation always exists, proceed by induction. The base case is clear and now suppose the result holds for all . Let be the largest Fibonacci number less than or equal to . If then that is a Zeckendorf representation, so suppose . Then has a Zeckendorf representation by the inductive hypothesis, so . The are non-consecutive, and furthermore all of the are less than because if then which contradicts the minimality of . So this is a Zeckendorf representation.
The proof implies that the Zeckendorf representation can be found by always taking the largest Fibonacci number less than subtracting it out, and repeating the process.
This theorem has applications in coding theory.