math.wiki
Logic, proof and discrete math › Recurrence relations › The Fibonacci sequence
Open on the map
Discrete Mathematics and Proof · F.IF.A.3

The Fibonacci sequence

A sequence where each term is the sum of the two before it has no obvious formula. How can anything be proved about all of its terms?

You need
Generating a sequence from a ruleAlgebra 1
Unlocks
Setting up a recurrence from a counting problemDiscrete Mathematics and Proof
Where you are 6 in Recurrence relations
Logic, proof and discrete math6
Recurrence relations6
Closed form versus recursive formGenerating a sequence from a rule
The Fibonacci sequence
Setting up a recurrence from a counting problemSolving and checking a two-term recurrenceTwo-term recurrences with a repeated root

Why this exists

A rule that looks back one term, such as a_n = 2a_{n-1} + 1, can often be unwound into a formula (Closed form versus recursive form). The simplest rule that looks back two terms, “add the last two”, already resists that: its closed formula involves \displaystyle \sqrt{5} and is the subject of Solving and checking a two-term recurrence. Yet the sequence it builds is full of exact patterns about squares, products, divisors and sizes. Every one of them has to be proved straight from the rule, which makes this sequence the standard place to practice induction with two base cases.

Earlier lessons have already met it: Generating a sequence from a rule counted its odd terms and found it in a bee family tree (Exercises 7 and 16 there), How induction works: base case, hypothesis and step proved F_1 + F_2 + \cdots + F_n = F_{n+2} - 1 (Exercise 24 there), and Strong induction and well-ordering bounded other rules that look back two or three terms. This lesson collects the main facts and proves them.

Definition

The Fibonacci sequence starts with two ones, and every later term is the sum of the two terms before it:

\begin{aligned} &F_1 = 1, \qquad F_2 = 1, \\ &F_n = F_{n-1} + F_{n-2} \ \text{ for } n \ge 3. \end{aligned}

The terms F_n are the Fibonacci numbers. Running the rule backward once, F_2 = F_1 + F_0 forces F_0 = 0; some results below are neater with F_0 allowed. The sequence is named for Leonardo of Pisa, known as Fibonacci, whose book Liber Abaci introduced it to European readers.

nF_nnF_n
111189
2112144
3213233
4314377
5515610
6816987
713171597
821182584
934194181
1055206765

Two starting values are needed because the rule reaches back two places. For the same reason, a proof by induction about F_n usually checks two base cases and assumes the claim for the two previous indices, which is Strong induction and well-ordering.

Intuition

Lay down a 1 by 1 square, then another beside it, making a 1 by 2 rectangle. Along its long side lay a 2 by 2 square: now the rectangle is 2 by 3. Along that long side lay a 3 by 3 square, giving 3 by 5, and so on. At each stage the rectangle is F_n by F_{n+1}, and the new square has side F_{n+1}, so the next rectangle is F_{n+1} by F_n + F_{n+1} = F_{n+2}. The rule “add the last two” is exactly what keeps the squares fitting.

1 1 2 3 5 8 13 8
Figure 1Squares of sides F_1 to F_6 tile an F_6 by F_7 rectangle, so 1 + 1 + 4 + 9 + 25 + 64 = 8 \cdot 13. Each new square is laid along the long side of the rectangle so far.

Counting area two ways gives the first identity below: the squares add to the rectangle.

The rule also controls size. Since F_{n-2} \le F_{n-1}, each term is at most double the one before. Since F_{n-1} \le 2F_{n-2}, each term is at least \displaystyle 1 + \frac{1}{2} times the one before (from n = 3 on). So the terms grow roughly like a power, with ratio somewhere between \displaystyle \frac{3}{2} and 2.

Results

Sum of squares. For every n \ge 1, F_1^2 + F_2^2 + \cdots + F_n^2 = F_n F_{n+1}.

Cassini’s identity. For every n \ge 2, F_{n-1}F_{n+1} - F_n^2 = (-1)^n.

Addition rule. For all m \ge 1 and n \ge 1 (using F_0 = 0),

F_{m+n} = F_m F_{n+1} + F_{m-1} F_n.

Consecutive terms are coprime. \gcd(F_n, F_{n+1}) = 1 for every n \ge 1.

Divisibility. F_m \mid F_{mn} for all positive integers m and n. In particular F_3 = 2 divides F_n exactly when 3 \mid n.

Growth. For every n \ge 1, \displaystyle \left(\frac{3}{2}\right)^{n-2} \le F_n < 2^n.

Zeckendorf’s theorem. Every positive integer is a sum of distinct Fibonacci numbers F_k with k \ge 2, no two of them with consecutive indices, and this representation is unique.

Why it is true

Proof of the sum of squares. Induction on n. For n = 1: F_1^2 = 1 = F_1F_2. Suppose F_1^2 + \cdots + F_k^2 = F_kF_{k+1} for some k \ge 1. Adding F_{k+1}^2 gives F_kF_{k+1} + F_{k+1}^2 = F_{k+1}(F_k + F_{k+1}) = F_{k+1}F_{k+2}, which is the claim for k + 1. \square This is the figure in algebra: one base case suffices because the step uses the rule only once, at index k + 2.

Proof of Cassini’s identity. Induction on n. For n = 2: F_1F_3 - F_2^2 = 2 - 1 = 1 = (-1)^2. Suppose F_{k-1}F_{k+1} - F_k^2 = (-1)^k for some k \ge 2. Replace F_{k+2} by F_{k+1} + F_k, and then one factor F_{k+1} by F_k + F_{k-1}:

\begin{aligned} F_kF_{k+2} - F_{k+1}^2 &= F_kF_{k+1} + F_k^2 - F_{k+1}^2 \\ &= F_kF_{k+1} + F_k^2 - F_{k+1}(F_k + F_{k-1}) \\ &= -\left(F_{k-1}F_{k+1} - F_k^2\right) = (-1)^{k+1}. \end{aligned}

\square

Proof that consecutive terms are coprime. The key lemma of The Euclidean algorithm and coprime numbers says that if a = bq + r then \gcd(a, b) = \gcd(b, r). Since F_{n+1} = 1 \cdot F_n + F_{n-1} for n \ge 2, \gcd(F_{n+1}, F_n) = \gcd(F_n, F_{n-1}). Applying this down to n = 2 (formally, induction on n) gives \gcd(F_{n+1}, F_n) = \gcd(F_2, F_1) = 1. \square Cassini’s identity gives a second proof: a common divisor of F_n and F_{n+1} divides F_{n-1}F_{n+1} - F_n^2 = \pm 1.

The addition rule, divisibility and growth are proved in Examples 3 to 5.

Proof of Zeckendorf’s theorem, existence. Strong induction on the positive integer N. If N = 1, then N = F_2. Let N \ge 2 and assume every positive integer below N has such a representation. Let F_k be the largest Fibonacci number with F_k \le N; then k \ge 3 and N < F_{k+1}. If N = F_k we are done. Otherwise r = N - F_k satisfies 0 < r < N and

r < F_{k+1} - F_k = F_{k-1}.

By the hypothesis r is a sum of distinct, nonconsecutive Fibonacci numbers, each at most r < F_{k-1}, so each has index at most k - 2. Adding F_k keeps the indices distinct and nonconsecutive. \square

Uniqueness. Exercise 17 shows that a sum of nonconsecutive F_j (indices at least 2) whose largest term is F_k is less than F_{k+1}. Suppose N had two different representations. Delete the terms they share; what is left are two different nonconsecutive sets with the same sum, neither empty (a nonempty set has positive sum). Let their largest terms be F_j and F_k, with j < k say. Then the first sum is below F_{j+1} \le F_k, which is at most the second sum, a contradiction. \square

Worked examples

Example 1

Tekle’s number

Tekle writes 750 as a sum of nonconsecutive Fibonacci numbers by always taking the largest one that fits. Carry this out, and check that the indices are nonconsecutive.

Solution

From the table and F_{16} = 987 > 750, the largest Fibonacci number at most 750 is F_{15} = 610, leaving 140. Then F_{11} = 89 leaves 51; F_9 = 34 leaves 17; F_7 = 13 leaves 4; F_4 = 3 leaves 1 = F_2. So

\begin{aligned} 750 &= 610 + 89 + 34 + 13 + 3 + 1 \\ &= F_{15} + F_{11} + F_9 + F_7 + F_4 + F_2. \end{aligned}

The indices 15, 11, 9, 7, 4, 2 have no two consecutive, as the existence proof promised: each leftover is below the Fibonacci number just under the one removed (140 < F_{14} = 377, and so on). By uniqueness, no other nonconsecutive sum gives 750. Dropping the condition allows others: 13 = 8 + 5 gives 750 = 610 + 89 + 34 + 8 + 5 + 3 + 1, where F_6 and F_5 are consecutive.

Example 2

A term far down the list

Find F_{30} from the table using the addition rule, and say what it shows about F_{15}.

Solution

Take m = n = 15 in the addition rule:

\begin{aligned} F_{30} &= F_{15}F_{16} + F_{14}F_{15} = F_{15}\,(F_{16} + F_{14}) \\ &= 610 \cdot (987 + 377) = 610 \cdot 1364 = 832{,}040. \end{aligned}

Check by continuing the table: F_{28} = 317{,}811 and F_{29} = 514{,}229, whose sum is 832{,}040. The factored form shows F_{15} \mid F_{30}, a first case of the divisibility result.

Example 3

Proving the addition rule

Prove that F_{m+n} = F_mF_{n+1} + F_{m-1}F_n for all m \ge 1 and n \ge 1.

Solution

Proof. Fix m \ge 1 and let P(n) be the statement F_{m+n} = F_mF_{n+1} + F_{m-1}F_n. The step will use two earlier cases, so check two bases. For n = 1, the right side is F_m \cdot 1 + F_{m-1} \cdot 1 = F_{m+1}, by the rule at index m + 1 (for m = 1 this is F_2 = F_1 + F_0). For n = 2, it is 2F_m + F_{m-1} = F_m + F_{m+1} = F_{m+2}.

Now let n \ge 1 and assume P(n) and P(n + 1). Add them, then apply the rule in each column:

\begin{aligned} F_{m+n+2} &= F_{m+n+1} + F_{m+n} \\ &= F_m(F_{n+2} + F_{n+1}) + F_{m-1}(F_{n+1} + F_n) \\ &= F_mF_{n+3} + F_{m-1}F_{n+2}, \end{aligned}

which is P(n + 2). By strong induction P(n) holds for every n \ge 1, and m was arbitrary. \square

Check. m = 4, n = 5: F_4F_6 + F_3F_5 = 3 \cdot 8 + 2 \cdot 5 = 34 = F_9.

Example 4

Terms at multiples of an index

Prove that F_m \mid F_{mn} for all positive integers m and n, and deduce that F_n is even exactly when 3 \mid n.

Solution

Proof. Fix m and induct on n. For n = 1, F_m \mid F_m. Suppose F_m \mid F_{mk}. The addition rule with mk in the first place and m in the second gives

F_{mk+m} = F_{mk}F_{m+1} + F_{mk-1}F_m.

The first term is a multiple of F_{mk}, hence of F_m; the second is a multiple of F_m. So F_m \mid F_{m(k+1)}. \square

With m = 3: F_3 = 2 divides F_{3k}, so every third term is even. For the converse, let n = 3k + r with r = 1 or 2. If k = 0 then F_n = 1 is odd. If k \ge 1, the addition rule gives F_n = F_{3k}F_{r+1} + F_{3k-1}F_r. Here F_{3k} is even and coprime to F_{3k-1}, so F_{3k-1} is odd, and F_r = 1. So F_n is even plus odd, which is odd. This is the odd, odd, even pattern of Generating a sequence from a rule, now as a consequence of divisibility.

Example 5

How big is the hundredth term?

Prove that \displaystyle \left(\frac{3}{2}\right)^{n-2} \le F_n < 2^n for every n \ge 1, and use it to bound the number of digits of F_{100}.

Solution

Proof. Strong induction with bases n = 1 and n = 2: \displaystyle \frac{2}{3} \le 1 < 2 and 1 \le 1 < 4. Let n \ge 3 and assume both bounds for all smaller indices. The upper bound is the argument of Strong induction and well-ordering: F_n < 2^{n-1} + 2^{n-2} < 2^n. For the lower bound,

\begin{aligned} F_n &\ge \left(\tfrac{3}{2}\right)^{n-3} + \left(\tfrac{3}{2}\right)^{n-4} \\ &= \left(\tfrac{3}{2}\right)^{n-4}\left(\tfrac{3}{2} + 1\right) \\ &= \left(\tfrac{3}{2}\right)^{n-4} \cdot \tfrac{10}{4} \\ &\ge \left(\tfrac{3}{2}\right)^{n-4} \cdot \tfrac{9}{4} = \left(\tfrac{3}{2}\right)^{n-2}. \end{aligned}

\square

For n = 100: \log_{10} 1.5 \approx 0.1761, so 1.5^{98} \approx 10^{17.26} > 10^{17}, and F_{100} has at least 18 digits. Also 2^{100} \approx 1.27 \cdot 10^{30} < 10^{31}, so at most 31 digits. The true value has 21:

F_{100} = 354{,}224{,}848{,}179{,}261{,}915{,}075.

The bounds trap the size without any formula for F_n.

Boundaries

  • The indices matter. Cassini’s identity starts at n = 2 (or n = 1 with F_0 = 0), and the addition rule needs F_0 when m = 1. Books that start the list F_0 = 1, F_1 = 1 shift every identity by one index. Here F_0 = 0, F_1 = F_2 = 1 throughout.
  • The starting values matter. The rule alone does not fix the identities. Start with 2, 5 instead and Cassini’s right side becomes \pm 11 (Exercise 19), and divisibility fails: the second term 5 does not divide the fourth, 12.
  • The converse of divisibility needs m \ge 3. F_1 = F_2 = 1 divide every term, so F_2 \mid F_3 although 2 \nmid 3. For m \ge 3 it is true that F_m \mid F_n only when m \mid n; this is stated here without proof.
  • Zeckendorf needs both conditions. Without “nonconsecutive”, uniqueness fails (Example 1). The value 1 appears twice in the sequence, so the theorem uses F_2 and never F_1. Zero is not covered.
  • Bounds are not a formula. They give the size of F_n to within a factor that grows with n. The exact formula is in Solving and checking a two-term recurrence.

Where this goes next

Counting problems produce this sequence again and again, for example tilings with squares and dominoes and strings with no two 1s in a row; Setting up a recurrence from a counting problem sets up those recurrences. Solving and checking a two-term recurrence finds the closed formula with the golden ratio. In The Euclidean algorithm and coprime numbers, consecutive Fibonacci numbers such as 987 and 610 are the slowest inputs, because every quotient is 1: that is the rule F_{n+1} = 1 \cdot F_n + F_{n-1} read as a division.

Exercises

Computing with the rule

  1. Extend the table: find F_{21} to F_{25}.
  2. Run the rule backward from F_1 = 1 and F_0 = 0 using F_{n-2} = F_n - F_{n-1} to find F_{-1} to F_{-5}. What pattern links F_{-n} and F_n?
  3. Write 200 and 1234 as sums of nonconsecutive Fibonacci numbers.
  4. Check Cassini’s identity for n = 12 and n = 13.
  5. Use the addition rule to find F_{40} from F_{19}, F_{20} and F_{21}.
  6. Find F_1^2 + F_2^2 + \cdots + F_{15}^2 and F_{10}^2 + F_{11}^2 + \cdots + F_{15}^2 without adding squares.

Divisors and common divisors

  1. Without computing F_{60}, list every F_m with m < 60 and F_m > 1 that the divisibility result shows divides it.
  2. Prove that \gcd(F_n, F_{n+2}) = 1 for every n \ge 1.
  3. Prove that \gcd(F_n, F_{n+3}) is 2 when 3 \mid n and 1 otherwise.
  4. Prove that 8 \mid F_n exactly when 6 \mid n.

Growth

  1. Prove that F_n \le 2^{n-2} for every n \ge 2.
  2. Use the growth bounds to find a range of n guaranteed to contain the smallest n with F_n > 10^6, then find that n exactly.
  3. Prove that F_n \ge 2^{n/2} for every n \ge 6, and show that it fails for n = 5.

Reasoning and proof

  1. Prove that F_{n+1}^2 - F_n^2 = F_{n-1}F_{n+2} for every n \ge 2.
  2. Prove that 3F_n = F_{n+2} + F_{n-2} for every n \ge 3.
  3. Refute with a counterexample: “If n is an odd prime, then F_n is prime.”
  4. Prove that if F_k is the largest term in a sum of distinct Fibonacci numbers with indices at least 2, no two consecutive, then the sum is less than F_{k+1}.
  5. Prove that if n \ge 5 and F_n is prime, then n is prime. Why is n = 4 excluded?
  6. Let G_1 = 2, G_2 = 5 and G_n = G_{n-1} + G_{n-2} for n \ge 3. Compute G_{n-1}G_{n+1} - G_n^2 for n = 2, 3, 4, 5, then prove that it equals 11(-1)^{n+1} for every n \ge 2.
Answers
  1. F_{21} = 10{,}946, F_{22} = 17{,}711, F_{23} = 28{,}657, F_{24} = 46{,}368, F_{25} = 75{,}025, each the sum of the two before.
  2. F_{-1} = 1, F_{-2} = -1, F_{-3} = 2, F_{-4} = -3, F_{-5} = 5. For example F_{-1} = F_1 - F_0 = 1 and F_{-2} = F_0 - F_{-1} = -1. The pattern is F_{-n} = (-1)^{n+1}F_n.
  3. 200 = 144 + 55 + 1, that is F_{12} + F_{10} + F_2, and 1234 = 987 + 233 + 13 + 1, that is F_{16} + F_{13} + F_7 + F_2, by taking the largest Fibonacci number that fits each time.
  4. n = 12: F_{11}F_{13} - F_{12}^2 = 89 \cdot 233 - 144^2, which is 20{,}737 - 20{,}736 = 1. n = 13: F_{12}F_{14} - F_{13}^2 = 144 \cdot 377 - 233^2, which is 54{,}288 - 54{,}289 = -1.
  5. With m = n = 20: F_{40} = F_{20}(F_{21} + F_{19}), which is 6765 \cdot 15{,}127 = 102{,}334{,}155.
  6. F_{15}F_{16} = 610 \cdot 987 = 602{,}070. Subtracting F_1^2 + \cdots + F_9^2 = F_9F_{10} = 1870 gives 600{,}200.
  7. The divisors of 60 are 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60, so F_m \mid F_{60} for each. Above 1: 2, 3, 5, 8, 55, 144, 610, 6765, 832{,}040.
  8. Proof. F_{n+2} = 1 \cdot F_n + F_{n+1}, so by the key lemma \gcd(F_{n+2}, F_n) = \gcd(F_n, F_{n+1}) = 1. \square
  9. Proof. F_{n+3} = F_{n+2} + F_{n+1} = F_n + 2F_{n+1}, so a common divisor d of F_n and F_{n+3} divides 2F_{n+1}. For n \ge 2, Cassini times 2 reads F_{n-1} \cdot 2F_{n+1} - 2F_n \cdot F_n = \pm 2, so d \mid 2 and the gcd is 1 or 2. It is 2 exactly when both are even. If 3 \mid n then 3 \mid n + 3 and both are even; if 3 \nmid n then F_n is odd. For n = 1, \gcd(1, 3) = 1. \square
  10. Proof. If 6 \mid n then F_6 = 8 divides F_n. Otherwise n = 6k + r with 1 \le r \le 5. If k = 0, F_n \in \{1, 1, 2, 3, 5\}. If k \ge 1, the addition rule gives F_n = F_{6k}F_{r+1} + F_{6k-1}F_r, so F_n - F_{6k-1}F_r is a multiple of 8. Here F_{6k} is even and coprime to F_{6k-1}, so F_{6k-1} is odd, and F_r is 1, 1, 2, 3 or 5. So F_{6k-1}F_r is odd or twice an odd number, never a multiple of 8, and neither is F_n. \square
  11. Proof. Bases: F_2 = 1 = 2^0, F_3 = 2 = 2^1. For n \ge 4, assuming the bound below n: F_n \le 2^{n-3} + 2^{n-4} = 3 \cdot 2^{n-4} < 4 \cdot 2^{n-4} = 2^{n-2}. \square
  12. F_n < 2^n \le 2^{19} = 524{,}288 for n \le 19, so n \ge 20. Since 1.5^{35} \approx 1.46 \cdot 10^6, F_n > 10^6 once n - 2 \ge 35, so n \le 37. Continuing the table: F_{30} = 832{,}040 and F_{31} = 1{,}346{,}269, so n = 31.
  13. Proof. Bases: F_6 = 8 = 2^3, and F_7 = 13 \ge 2^{7/2} because 13^2 = 169 \ge 128 = 2^7. For n \ge 8: F_n = F_{n-1} + F_{n-2} \ge 2F_{n-2} \ge 2 \cdot 2^{(n-2)/2} = 2^{n/2}, using F_{n-1} \ge F_{n-2}. \square For n = 5: F_5^2 = 25 < 32 = 2^5, so 5 < 2^{5/2}.
  14. Proof. Factor the difference of squares: (F_{n+1} - F_n)(F_{n+1} + F_n) = F_{n-1}F_{n+2}, since F_{n+1} - F_n = F_{n-1} and F_{n+1} + F_n = F_{n+2} by the rule. \square
  15. Proof. F_{n+2} = F_{n+1} + F_n = 2F_n + F_{n-1} and F_{n-2} = F_n - F_{n-1}. Adding gives 3F_n. \square
  16. n = 19: F_{19} = 4181 = 37 \cdot 113. (The odd primes 3, 5, 7, 11, 13, 17 give the primes 2, 5, 13, 89, 233, 1597, which is why the claim looks plausible.)
  17. Proof. Strong induction on k. For k = 2 the sum is F_2 = 1 < 2 = F_3; for k = 3 it is F_3 = 2 < 3 = F_4, since F_2 is consecutive to F_3 and cannot appear. For k \ge 4, the other terms have indices at most k - 2, so by the hypothesis they sum to less than F_{k-1} (or to 0). The whole sum is less than F_k + F_{k-1} = F_{k+1}. \square
  18. Proof. Suppose n \ge 5 is composite, n = ab with 2 \le a \le b < n. Then b \ge 3, since a = b = 2 gives n = 4. By divisibility F_b \mid F_n, and 2 \le F_b < F_n because the terms strictly increase from F_2 on. So F_n is not prime. \square For n = 4, F_4 = 3 is prime but 4 is not; the only factorization 2 \cdot 2 gives F_2 = 1.
  19. G = 2, 5, 7, 12, 19, 31. The values are 2 \cdot 7 - 25 = -11, 5 \cdot 12 - 49 = 11, 7 \cdot 19 - 144 = -11, 12 \cdot 31 - 361 = 11. Proof. The base n = 2 gives -11 = 11(-1)^3. The algebra in the proof of Cassini’s identity used only the rule, so it shows G_kG_{k+2} - G_{k+1}^2 = -(G_{k-1}G_{k+1} - G_k^2); each step flips the sign. \square
kg1128 · updated 2026-10-22 · CC-BY-SA-4.0