maths.free › Number Theory › Sequences

Sequences

Fibonacci, recurrences and closed forms.

A sequence defined by a rule from earlier terms is a recurrence. The Fibonacci numbers are the classic: each is the sum of the previous two. Many recurrences have a closed form — for Fibonacci it involves the golden ratio — but computing them term by term is often the clearest path.

Worked example: fib(20)

Number-Theory · Sequences

Fib(20)

20

Step by step

  1. F_0 = 0,; F_1 = 1

    Each Fibonacci number is the sum of the two before it.

  2. F_{2} = F_{1} + F_{0} = 1

  3. F_{3} = F_{2} + F_{1} = 2

  4. F_{4} = F_{3} + F_{2} = 3

  5. F_{5} = F_{4} + F_{3} = 5

  6. F_{6} = F_{5} + F_{4} = 8

  7. F_{7} = F_{6} + F_{5} = 13

  8. F_{8} = F_{7} + F_{6} = 21

  9. \vdots

  10. F_{19} = F_{18} + F_{17} = 4181

  11. F_{20} = F_{19} + F_{18} = 6765

Reveal the answer
F_{20} = 6765

Try your own

More in Number Theory

Prime factorisationPrime numbersGCD and LCMModular arithmeticDivisorsNumber bases