# Fibonacci Sequence

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

\[\begin{array} &F_1 = F_2 = 1, &F_n = F_{n-1} + F_{n-2}.\end{array}\]

The first few terms are

\[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \ldots.\]

#### Contents

## Closed-form Expression

Let \( \phi = \frac{1+\sqrt{5}}2 \) be the golden ratio. Let \( {\overline \phi} = \frac{-1}{\phi} = \frac{1-\sqrt{5}}2. \) Then

\[{ F }_{ n }= \frac { \phi^n-{\overline \phi}^n }{ \sqrt { 5 } } .\]

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 \( G_n = \frac { \phi^n-{\overline \phi}^n }{ \sqrt { 5 } } \). The goal is to prove that \( F_n=G_n\) by induction on \(n \). The base cases are \( G_1 = G_2 = 1 \), which is clear. Now suppose \( G_k=F_k \) for all \( k<n\), where \( n \) is at least \( 3 \). Then\[ \begin{align} F_n &= F_{n-1}+F_{n-2} \\&= G_{n-1}+G_{n-2} & \text{(inductive hypothesis)} \\ &= \frac1{\sqrt{5}} \Big(\phi^{n-1}-{\overline{\phi}}^{n-1}\Big)+\frac1{\sqrt{5}}\Big(\phi^{n-2}-{\overline{\phi}}^{n-2}\Big) \\ &= \frac1{\sqrt{5}} \Big(\phi^{n-1}+\phi^{n-2}-{\overline\phi}^{n-1}-{\overline\phi}^{n-2}\Big) \\ &= \frac1{\sqrt{5}} \Big(\phi^n-{\overline\phi}^n\Big) = G_n, \end{align} \]

where the last line comes from the fact that \( \phi\) and \(\overline\phi\) are the two roots of the equation \( x^2=x+1\). \(_\square\)

Note that for \( n \ge 1 \), the term \( \frac{{\overline\phi}^n}{\sqrt{5}} \) is small, certainly between \( -0.3 \) and \( 0.3\). So \( F_n \) is the nearest integer to \( \frac{\phi^n}{\sqrt{5}} \).

We have

\[\frac{\phi^{10}}{\sqrt{5}} = 55.0036\ldots, \quad \frac{\phi^{11}}{\sqrt{5}} = 88.9977\ldots,\]

so \( F_{10} = 55 \) and \( F_{11} = 89\).

The ratios of successive Fibonacci numbers should therefore be roughly

\[\displaystyle \phi =\lim _{ n\rightarrow \infty }{ \frac { { F }_{ n+1 } }{ { F }_{ n } } } = \frac{1+\sqrt5}{2}.\]

This can be proved easily using Binet's formula.

We have

\[ \begin{align} \frac{F_{n+1}}{F_n} &= \frac{\phi^{n+1}-{\overline{\phi}}^{n+1}}{\phi^n-{\overline{\phi}}^n} \\ &= \frac{\phi-\frac{{\overline{\phi}}^{n+1}}{\phi^n}}{1-\frac{{\overline{\phi}}^n}{\phi^n}}, \end{align} \]

and the terms \( \frac{{\overline{\phi}}^{n+1}}{\phi^n} \) and \( \frac{{\overline{\phi}}^n}{\phi^n} \) approach \( 0 \) as \( n \to \infty \), because the numerator approaches \( 0 \) and the denominator approaches \( \infty \).

Therefore, the limit is \( \frac{\phi}1 = \phi \). \(_\square\)

## Continued Fraction

The Fibonacci sequence appears as the numerators and denominators of the convergents to the simple continued fraction

\[ [1,1,1,\ldots] = 1+\frac1{1+\frac1{1+\frac1{\ddots}}}. \]

This continued fraction equals \( \phi,\) since it satisfies \( x = 1+\frac1{x} \) (and it is greater than 1).

The \( n^\text{th}\) convergent to this continued fraction is \( \frac{F_{n+1}}{F_n} \), so this gives another proof that \( \lim\limits_{n\to\infty} \frac{F_{n+1}}{F_n} = \phi \).

## Enumerative Problems

Like the Catalan numbers, the Fibonacci numbers count many types of combinatorial objects. Here are four examples.

(1) \( F_n \) is the number of compositions of \( n-1 \) consisting of \( 1\)s and \( 2\)s. (A composition of \(n-1\) is an expression of \( n-1\) as a sum of parts, where the order of the parts matters.) For instance,

\[ \begin{align} 5 &= 1+1+1+1+1\\&=1+1+1+2\\&=1+1+2+1\\&=1+2+1+1\\&=2+1+1+1 \\&=1+2+2\\&=2+1+2\\&=2+2+1, \end{align} \]

so \( F_6 = 8. \)

(2) \( F_n \) is the number of ways to tile a \( 2\times (n-1)\) board with \( 1\times 2\) dominoes.

(3) \( F_n \) is the number of binary sequences of length \( n-2\) with no consecutive \( 0\)s.

(4) \( F_n \) is the number of subsets of \( \{ 1,2,\ldots,n-2\} \) that do not contain any pair of consecutive numbers.

To see that the Fibonacci numbers count these objects, let the number of objects equal \( G_n \) and show that \( G_n=G_{n-1}+G_{n-2}\). Then verify that \( F_1=G_1\) and \( F_2 = G_2 \), and the proof is complete.

For instance, to prove (4), start with \( G_1=1, G_2 =1, G_3= 2, G_4 = 3 \), and then suppose \( S \) is a subset of \( \{1,2,\ldots,n-2\}\) without any consecutive numbers in it. There are \( G_{n-1} \) such sets \( S\) that don't contain \( n-2 \). If \( S \) contains \( n-2\), then it doesn't contain \( n-3\), so \( S \) is obtained by taking a subset of \( \{1,2,\ldots,n-4\} \) and throwing in \( n-2\). So there are \( G_{n-2}\) such sets \( S\). This proves that \( G_n = G_{n-1}+G_{n-2},\) as desired.

A composition of \( n \) is an expression of \( n \) as a sum of not necessarily distinct positive integers, where the order matters. Note that \( n = n \) counts as a composition of \( n \).

Let \( C_n \) be the number of *compositions* of \( n \) with no part equal to 1.

For instance, \( C_6 = 5 \) because \( 6 = 6 =4+2=3+3=2+4=2+2+2.\)

Find \( C_{15} \).

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?

**Clarification:**

- When he climbs from the \({ 9 }^\text{th}\) step to the \({ 10 }^\text{th},\) 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.

## Identities involving Fibonacci Series

There are quite a few identities relating different Fibonacci numbers. For instance,

\[ F_n^2-F_{n-1}F_{n+1} = (-1)^{n+1}, \]

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 \( n = 2,3 \), and now suppose that it is true for \( n \). Then

\[ \begin{align} F_{n+1}^2-F_nF_{n+2} &= F_{n+1}^2-F_n(F_n+F_{n+1})\\ &= F_{n+1}(F_{n+1}-F_n) - F_n^2 \\ &= F_{n+1}F_{n-1}-F_n^2 \\ &= -(-1)^{n+1} = (-1)^{n+2}, \end{align} \]

so it is true for \( n+1\). \(_\square\)

The proofs of the rest of these identities are similar.

(1) \( F_mF_n + F_{m-1}F_{n-1} = F_{m+n-1}\)

- (1a) \( F_{2n-1}=F_{n-1}^2+F_n^2 \)
- (1b) \( F_{2n} = F_n(F_{n-1}+F_{n+1}) \)
(2) \( F_1+F_2+F_3+\cdots+F_n = F_{n+2}-1 \)

(3) \( F_1+F_3+F_5+\cdots+F_{2n-1} = F_{2n} \) and \( F_2+F_4+F_6+\cdots+F_{2n}=F_{2n+1}-1 \)

(4) \( F_{n+1} = \sum\limits_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k} \)

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: \(1, 2, 3, 5, 8, 13,\ldots.\)

The slow turtle could roll in an increasing distance of an arithmetic sequence of 1-interval as shown: \(1, 2, 3, 4, 5,\ldots\)

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 \(3\) sticks that can form a triangle. If the set has two sticks of length \(1\), which are the smallest, what is the least possible length of the \({ 14 }^\text{th}\) stick?

## Generating Function

The generating function of the Fibonacci numbers is

\[ \sum_{n=1}^\infty F_n x^n = \frac{x}{1-x-x^2}. \]

This follows from the expansion:

\[\begin{align} \big(1-x-x^2\big)\big(F_1x + F_2x^2 + F_3x^3 + \cdots\big) &= F_1x + (F_2-F_1)x^2+(F_3-F_2-F_1)x^3+(F_4-F_3-F_2)x^4+ \cdots \\ &= x+0x^2+\sum_{k=3}^\infty (F_k-F_{k-1}-F_{k-2})x^k \\ &= x.\ _\square \end{align}\]

\[ \frac{1}{10}+ \frac{1}{10^2}+ \frac{2}{10^3}+ \frac{3}{10^4}+ \frac{5}{10^5}+ \frac{8}{10^6}+ \cdots \]

Find the sum of the above fractions, where the denominators follow a geometric progression and the numerators follow the Fibonacci sequence.

If your answer is \(\frac{A}{B}\), where \(A\) and \(B\) are coprime positive integers, submit your answer as \(A+B\).

\[ \begin{eqnarray} 0. && 00000 \quad 00001 \quad 00001 \quad 00002 \quad 00003 \quad 00005 \quad 00008 \\ && 00013 \quad 00021 \quad 00034 \quad 00055 \quad 00089\quad 00144\quad \ldots \\ \end{eqnarray} \]

The above shows the first few digits (actually 65) of the decimal representation of the fraction \( \large \frac1{9,999,899,999}. \) If we split the digits into partitions of 5, we can see that the numbers form a Fibonacci sequence: \(0,1,1,2,3,5,8,13,\ldots \). How many positive Fibonacci numbers can we find before the pattern breaks off?

**Note:** For example, suppose that the fraction equals \[0.00000 \quad 00001 \quad 00001 \quad 00002 \quad 00003 \quad 00009 \ldots \] instead of the one given at the top. Then you could only find the first five Fibonacci numbers, namely \(0,1,1,2,3\). 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.

## Divisibility Properties

Identity (1) above can be used to show that if \( a|b \), then \( F_a|F_b\). In fact, more is true:

\[ \text{gcd}(F_a,F_b) = F_{\text{gcd}(a,b)}. \]

This follows from (1) and a process similar to the Euclidean algorithm; write \( a = bq+r, \, 0 \le r < b, \) and then

\[ \begin{align} \text{gcd}(F_a,F_b) &= \text{gcd}(F_{bq+r},F_b) \\ &= \text{gcd}(F_{bq}F_{r+1}+F_{bq-1}F_r,F_b) \\ &= \text{gcd}(F_{bq-1}F_r,F_b) &&\qquad (\text{because } F_b|F_{bq}) \\ &= \text{gcd}(F_r,F_b), &&\qquad \big(\text{because gcd} (F_{bq-1},F_{bq})=1\big) \end{align} \]

and so on.

We have \( \text{gcd}(F_{10},F_{15}) = \text{gcd}(55,610)=5=F_5. \)

Note that this discussion implies that if \( F_p \) is prime, then \( p \) is prime or \( p =4 \). The converse is not true \((F_2 = 1, F_{19} = 37 \cdot 113), \) and in fact it is not known whether there are infinitely many primes \( p \) such that \( F_p \) is prime.

## Zeckendorf's Theorem

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, \( 41 = 34+5+2 \) is a Zeckendorf representation of \( 41 \).

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 \( F_n \) cannot be larger than \( F_{n+1} \) \((\)note that \( F_1 \) and \( F_3 \) are consecutive Fibonacci numbers since \( F_1 = F_2). \) 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 \( F_a \) and the largest Fibonacci number in the second sum is \(F_b\); suppose without loss of generality that \( a < b \). Then the first sum is less than \( F_{a+1} \) but the second sum is clearly \( \ge F_b \), so they cannot be equal.

To see that a Zeckendorf representation always exists, proceed by induction. The base case is clear \((1=1,2=2),\) and now suppose the result holds for all \( k < n \). Let \( F_a \) be the largest Fibonacci number less than or equal to \( n \). If \( F_a = n,\) then that is a Zeckendorf representation, so suppose \( F_a < n \). Then \( n-F_a \) has a Zeckendorf representation \( F_{b_1}+F_{b_2} + \cdots + F_{b_k} \) by the inductive hypothesis, so \( n =F_a + F_{b_1}+F_{b_2}+\cdots+F_{b_k} \). The \( b_i \) are non-consecutive, and furthermore all of the \( b_i \) are less than \( a-1, \) because if \( n-F_a \ge F_{a-1}, \) then \( n \ge F_a + F_{a-1} = F_{a+1}, \) which contradicts the minimality of \( a \). So this is a Zeckendorf representation. \(_\square\)

The proof implies that the Zeckendorf representation can be found by always taking the largest Fibonacci number less than \( n,\) subtracting it out, and repeating the process.

This theorem has applications in coding theory.

**Cite as:**Fibonacci Sequence.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/fibonacci-series/