The Fibonacci Sequence

The Fibonacci sequence (OEIS A000045) is defined as follows:

Its first few terms are:

The Lucas Sequence

The Lucas sequence (OEIS A000032) is defined as follows:

Its first few terms are:

The Lucas sequence is often used as a tool when studying the Fibonacci sequence.

Closed Form of the Fibonacci Sequence

The $n$-th Fibonacci number can be computed from the recurrence in \Theta(n) time. However, faster methods are available. $\Theta (n)$

Closed-Form Solution

The closed-form solution is a formula-based solution. The general formula for the Fibonacci sequence, known as Binet's formula, is

This formula is easy to prove by induction. It can also be derived using generating functions or by solving an equation.

The second term in the numerator always has absolute value less than $1$ and decreases exponentially. Therefore, the formula can be written as

Here the square brackets mean the nearest integer.

Both formulas require extremely high precision in computation, so they are rarely used in practice. Nevertheless, together with quadratic residues and inverses modulo an integer, they are still useful in OI.

Closed Form of the Lucas Sequence

The Lucas sequence has the closed form

which is very similar to the Fibonacci formula. In fact,

That is, $L_n$ and $F_n$ are precisely the numerator coefficients obtained after expanding $\left(\frac{1 + \sqrt{5}}{2}\right)^n$ binomially and collecting like terms. Thus, all solutions of the Pell equation

are exactly

namely the Lucas and Fibonacci sequences. Consequently,

Matrix Form

The Fibonacci recurrence can be expressed through matrix multiplication:

Let $P = \begin{bmatrix}0 & 1 \cr 1 & 1 \cr\end{bmatrix}$. Then

Thus, matrix multiplication computes Fibonacci numbers in $\Theta(\log n)$ time. The formula from the preceding section can also be obtained by diagonalizing the matrix.

Fast Doubling

The method above yields

Therefore, two adjacent Fibonacci numbers can be computed quickly, with a smaller constant than matrix exponentiation. The following code returns the pair $(F_n,F_{n+1})$.

pair<int, int> fib(int n) {
  if (n == 0) return {0, 1};
  auto p = fib(n >> 1);
  int c = p.first * (2 * p.second - p.first);
  int d = p.first * p.first + p.second * p.second;
  if (n & 1)
    return {d, c + d};
  else
    return {c, d};
}

Properties

The Fibonacci sequence has many interesting properties. Some simple ones are listed below:

1. Cassini's identity: $F_{n-1} F_{n+1} - F_n^2 = (-1)^n$.
2. Addition identity: $F_{n+k} = F_k F_{n+1} + F_{k-1} F_n$.
3. Setting $k = n$ in the preceding identity gives $F_{2n} = F_n (F_{n+1} + F_{n-1})$.
4. By induction from the preceding identity, $\forall k\in \mathbb{N},F_n|F_{nk}$.
5. The preceding property has a converse: $\forall F_a|F_b,a|b$.
6. GCD identity: $(F_m, F_n) = F_{(m, n)}$.
7. Taking two adjacent Fibonacci numbers as input makes the Euclidean algorithm attain its worst-case complexity (see Wikipedia - Lamé for details).

Relationship between the Fibonacci and Lucas Sequences

Identities for the Lucas and Fibonacci sequences are strikingly similar to trigonometric identities. For example,

resembles

and

resembles

Thus, the Lucas sequence is similar to the cosine function, while the Fibonacci sequence is similar to the sine function. From

we obtain the identities for the sum of two indices:

and hence the doubling identities:

These also provide a way to double indices quickly. In the same way, by imitating trigonometric identities such as parity, sum-to-product, product-to-sum, half-angle formulas, and universal substitutions, we can derive more corresponding identities for the Lucas and Fibonacci sequences.

Fibonacci Coding

The Fibonacci sequence can encode positive integers. By Zeckendorf's theorem, every natural number $n$ has a unique representation as a sum of Fibonacci numbers:

where $k_1 \ge k_2 + 2,\ k_2 \ge k_3 + 2,\ \ldots,\ k_r \ge 2$ (that is, two adjacent Fibonacci numbers cannot both be used).

We can therefore encode a positive integer as $d_0 d_1 d_2 \dots d_s 1$, where $d_i=1$ means that $F_{i+2}$ is used. A final 1 is forced at the end of the code, producing two adjacent 1s, to mark the end of the code. For example:

The encoding of $n$ can be found greedily:

1. Enumerate Fibonacci numbers from largest to smallest until reaching $F_i\le n$.
2. Subtract $F_i$ from $n$ and put a 1 at position $i-2$ in the code, numbered from left to right starting at 0.
3. If $n$ is positive, return to step 1.
4. Append a 1 at the end of the code to mark its end. $F_i$

Decoding is analogous: first remove the final 1; for every position $i$ containing a 1, numbered from left to right starting at 0, add $F_{i+2}$ to the answer. The final answer is the original number.

Periodicity Modulo m

By the pigeonhole principle, the Fibonacci sequence modulo m is periodic. Since each Fibonacci number depends on the preceding two values, the state is described by a pair of adjacent Fibonacci numbers. Consider the first $m^2+1$ pairs modulo $m$:

There are $m$ residue classes modulo $m$, so at most $m^2$ distinct pairs are possible. Hence two of the first $m^2+1$ pairs must be equal. The same Fibonacci sequence can then be generated from either pair, so the sequence is periodic and its smallest positive period is at most $m^2$.

Pisano Period

The smallest positive period of the Fibonacci sequence modulo $m$ is called the Pisano period (Pisano period, OEIS A001175). We denote it by $\pi(m)$. $m$

This observation can be used to compute the $n$-th Fibonacci number modulo $m$. If $n$ is very large, we need only compute a period modulo $m$, not necessarily the smallest positive period.

The following facts hold:

1. For coprime moduli $m_1,m_2$, $\pi(m_1m_2)=\operatorname{lcm}(\pi(m_1),\pi(m_2))$.
2. For a prime $p$ and positive integer $e$, $\pi(p^{e})\mid p^{e-1}\pi(p)$.
3. For $m=2^e~(e\in\mathbf N_+)$, $\pi(m)=3\cdot 2^{e-1}$.
4. For $m=5^e~(e\in\mathbf N_+)$, $\pi(m)=4\cdot 5^e$.
5. For a prime $p\equiv\pm1\pmod{10}$, $\pi(p)\mid(p-1)$; for a prime $p\equiv\pm3\pmod{10}$, $\pi(p)\mid 2(p+1)$.

Together these facts show that the Pisano period modulo $m$ is at most $6m$, with equality if and only if $m = 2\times 5^e~(e\in\mathbf N_+)$.

Using these facts and prime factorization, we obtain the following fast method for computing a Pisano period:

// Get a period of Fibonacci sequence mod m.
// Not necessarily be the exact Pisano period.
uint32_t calc_cycle_from_mod(uint32_t m) {
  uint32_t res = 1;
  for (auto pe : factorize(m)) {
    auto p = pe.first;
    auto e = pe.second;
    uint64_t cur = pow(p, e - 1);
    if (p == 2) {
      cur *= 3;
    } else if (p == 5) {
      cur *= 20;
    } else if (p % 5 == 1 || p % 5 == 4) {
      cur *= p - 1;
    } else {
      cur *= 2 * (p + 1);
    }
    res = lcm(res, cur);
  }
  return res;
}

The period obtained this way may only be a multiple of the Pisano period. To obtain the exact period, we can further examine its divisors, or use the BSGS algorithm in $O(\sqrt{m})$ time.

Proof

We briefly prove the facts about the Pisano period above. The method below also generalizes to general second-order homogeneous linear recurrences with constant coefficients. Although the constants differ, their periods modulo $m$ are all $O(m)$.

First, by the Chinese remainder theorem, it suffices to consider prime-power moduli. Let $m_1,m_2$ be coprime. The periods modulo $m_1$ and $m_2$ are respectively multiples of $\pi(m_1)$ and $\pi(m_2)$, so the smallest positive period modulo $m_1m_2$ is \operatorname{lcm}(\pi(m_1),\pi(m_2)). This proves fact 1. $\pi(m_1)$ $\pi(m_2)$

The Pisano period modulo $m$ is also the smallest positive integer $k$ such that

In other words, it is the order of $A$ modulo $m$¹.

For $m=p^e$, let $k=\pi(p^e)$. There is a matrix $\Lambda$ such that

By the binomial theorem,

Thus, by the properties of orders, $\pi(p^{e+1})\mid kp = p\pi(p^e)$. Induction on $e$ gives $\pi(p^e)\mid p^{e-1}\pi(p)$.

For a prime modulus $p$, we give two proofs.

Using the Closed Form

Use

Expanding by the binomial theorem and eliminating radicals gives

For $p=2$, this expression cannot be reduced modulo p directly, but $\pi(2)=3$ can be verified. For $p=5$, $F_n\equiv n\cdot 3^{n-1}\pmod{p}$, and $\pi(5)=20$ follows directly. For the remaining odd primes:

• If $p\equiv 1,4\pmod{5}$, then

  $$\begin{aligned} F_{p} &\equiv \dfrac{1}{2^{p-1}}\binom{p}{p}5^{(p-1)/2} \equiv 1 \pmod{p},\\ F_{p+1} &\equiv \dfrac{1}{2^p}\left(\binom{p+1}{1} + \binom{p+1}{p}5^{(p-1)/2}\right) \equiv 1 \pmod{p}. \end{aligned}$$

  Here we use Lucas's theorem, Fermat's little theorem, and quadratic reciprocity: $\dbinom{p}{k}\equiv 0\pmod{p}$ for $0 < k < p$, $\dbinom{p+1}{k}\equiv 0\pmod{p}$ for $1 < k < p$, $2^{p-1}\equiv 5^{p-1}\equiv 1\pmod{p}$, and $5^{(p-1)/2} \equiv 1\pmod{p}$. Therefore $(F_p,F_{p+1}) \equiv (F_1,F_2) \pmod{p}$, so $(p-1)$ is a period and $\pi(p)\mid(p-1)$.

• If $p\equiv 2,3\pmod{5}$, then $p\equiv 1,4\pmod{5}$ $p$ $5$ $5$ $p$ $p$

  $$\begin{aligned} F_{2p} &\equiv \dfrac{1}{2^{2p-1}}\binom{2p}{p}5^{(p-1)/2} \equiv -1 \pmod{p},\\ F_{2p+1} &\equiv \dfrac{1}{2^{2p}}\left(\binom{2p+1}{1} + \binom{2p+1}{p}5^{(p-1)/2} + \binom{2p+1}{2p+1}5^p\right) \equiv -1\pmod{p}. \end{aligned}$$

  Lucas's theorem gives the required vanishing binomial coefficients and \dbinom{2p}{p}\equiv\dbinom{2p+1}{p}\equiv2\pmod{p}. Fermat's little theorem gives $2^{p-1}\equiv 5^{p-1}\equiv 1\pmod{p}$, while quadratic reciprocity gives $5^{(p-1)/2} \equiv -1\pmod{p}$. Hence $(F_{2p},F_{2p+1}) \equiv (F_{-2},F_{-1}) \pmod{p}$, so $2(p+1)$ is a period and $\pi(p)\mid 2(p+1)$. $0 < k < p$ $p < k < 2p$ $\dbinom{p}{k}\equiv 0\pmod{p}$ $\dbinom{2p}{p}\equiv 2\pmod{p}$ $1 < k < p$ $p + 1 < k < 2p$ $\dbinom{p}{k}\equiv 0\pmod{p}$ $\dbinom{2p+1}{p}\equiv 2\pmod{p}$ $p\equiv 2,3\pmod{5}$ $p$ $5$ $5$ $p$ $p$

This completes the proof. The limitation of this method is its heavy reliance on the closed form, which makes direct generalization difficult.

Using a Field Extension

Alternatively, compute the order of $A=\begin{pmatrix}1&1\\1&0\end{pmatrix}$ directly. Its characteristic polynomial is $f(x) = x^2-x-1$, with discriminant $\Delta = 5$. For $p=5$, $\Delta\equiv 0\pmod{5}$; $A$ has the repeated eigenvalue $\lambda=3$ and is not diagonalizable, so this case must be handled separately. For $p\equiv 1,4\pmod{5}$, quadratic reciprocity says that $\Delta=5$ is a quadratic residue modulo $p$. Thus $A$ has two distinct eigenvalues in $\mathbf F_p$, and its order divides $|\mathbf F_p^\times|=p-1$. For $p\equiv 2,3\pmod{5}$, $\Delta=5$ is a quadratic nonresidue modulo $p$. The two distinct eigenvalues lie in the field extension $\mathbf F_p[\sqrt{5}]$. Frobenius swaps them, so $\lambda_2=\lambda_1^p$ and $\lambda_1^{p+1}=\lambda_2^{p+1}=\lambda_1\lambda_2=-1$. Hence both eigenvalues have order dividing 2(p+1), so the order of $A$ divides $2(p+1)$. $\lambda_1\neq\lambda_2$ $\operatorname{lcm}(\operatorname{ord}(\lambda_1),\operatorname{ord}(\lambda_2))$ $A$ $\mathbf F_p$ $\lambda_1\neq\lambda_2$ $x\mapsto x^p$ $\lambda_1^{2(p+1)}=\lambda_2^{2(p+1)}=1$ $A$ $\operatorname{lcm}(\operatorname{ord}(\lambda_1),\operatorname{ord}(\lambda_2))$

Thus:

• $\pi(2^e)=\dfrac{3}{2}\cdot 2^e,~\dfrac{1}{4}\pi(5^e)=5^e$.
• If $p\equiv\pm1\pmod{10}$, then $\pi(p^e) \mid (p-1)p^{e-1}$, so $\pi(p^e)\le p^e$.
• If $p\equiv\pm3\pmod{10}$, then $\dfrac{1}{4}\pi(p^e) \mid \dfrac{p+1}{2}p^{e-1}$, so $\dfrac{1}{4}\pi(p^e)\le p^e$.

For $m=\prod_i p_i^{e_i}$, fact 1 gives

Therefore the Pisano period modulo $m$ is always at most $6m$, with equality exactly when $m=2\cdot 5^e$.

Exercises

• SPOJ - Euclid Algorithm Revisited
• SPOJ - Fibonacci Sum
• HackerRank - Is Fibo
• Project Euler - Even Fibonacci numbers
• Luogu P4000 The Fibonacci Sequence

References and Notes

• Fibonacci sequence - Wikipedia
• Zeckendorf's theorem - Wikipedia
• Pisano period - Wikipedia

This page is mainly translated from the blog post Числа Фибоначчи and its English translation Fibonacci Numbers. The Russian version is licensed under Public Domain + Leave a Link; the English version under CC-BY-SA 4.0. The content has been modified.