---
tag: 0GA9K57A39
kind: example
name: Fibonacci sequence
msc: [11B39]
sources:
  - url: https://en.wikipedia.org/wiki/Fibonacci_sequence
    locator: Definition
same_as:
  wikidata: Q23835349
  wikipedia: Fibonacci sequence
---

## Example

The Fibonacci sequence $(F_n)_{n \ge 0}$ is the sequence of natural numbers defined by
$$F_0 = 0, \qquad F_1 = 1, \qquad F_{n+2} = F_{n+1} + F_n.$$
It is an example of a sequence defined by a [[recurrence relation|07TZV87Y0T]], and in particular of a [[linear recurrence with constant coefficients|081THG13JZ]].
Its first terms are
$$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \dots$$

## Remarks

The ratios $F_{n+1} / F_n$ tend to the [[golden ratio|0SC8T7548D]] $\varphi = \frac{1 + \sqrt{5}}{2}$.
[[Binet's formula|0404D8TN7Y]] gives $F_n$ in closed form.
$F_{n+1}$ is the number of ways to tile a strip of length $n$ with squares of length $1$ and dominoes of length $2$.

## Explanations

### L1 human

Each Fibonacci number is the sum of the two before it: $5 + 8 = 13$, $8 + 13 = 21$, and so on.
The numbers grow by a factor close to $1.618$ at each step.