Fibonacci Numbers

$F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2}.$

Computing $F_n$

Method	Time	Use
Iteration	$O(n)$	$n\le 10^7$
Matrix power	$O(\log n)$	$n\le 10^{18}$
Fast doubling	$O(\log n)$	same, ~2× faster
Binet’s formula	$O(1)$	inexact beyond $n\approx 70$

Matrix form

$\left[\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}\right]={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n.$

Fast doubling — the better method

$F_{2k}=F_k(2F_{k+1}-F_k),F_{2k+1}=F_k^2+F_{k+1}^2.$

pair<long long,long long> fib(long long n, long long MOD) {   // returns {F(n), F(n+1)}
    if (n == 0) return {0, 1};
    auto [a, b] = fib(n >> 1, MOD);
    long long c = a * ((2 * b % MOD - a + MOD) % MOD) % MOD;
    long long d = (a * a + b * b) % MOD;
    return (n & 1) ? make_pair(d, (c + d) % MOD) : make_pair(c, d);
}

Half the multiplications of the matrix version, and no matrix struct.

Identities worth knowing

Identity
${\sum }_{i=0}^n{F}_i=F_{n+2}-1$
${\sum }_{i=0}^n{F}_i^2=F_n{F}_{n+1}$
$F_{m+n}=F_m{F}_{n+1}+F_{m-1}{F}_n$	the addition formula
$\gcd (F_m,F_n)=F_{\gcd (m,n)}$	strong divisibility
$F_n\mid F_{kn}$	corollary
$F_{n-1}{F}_{n+1}-F_n^2=(-1{)}^n$	Cassini’s identity
$F_n=\frac{{\varphi }^n-{\psi }^n}{\sqrt{5}}$	Binet, $\varphi =\frac{1+\sqrt{5}}{2}$
$F_n\approx {\varphi }^n/\sqrt{5}$	grows by a factor $\varphi \approx 1.618$ per step
$F_{93}$	the last one fitting in long long

The strong divisibility property $\gcd (F_m,F_n)=F_{\gcd (m,n)}$ is the most useful — it turns questions about common factors of Fibonacci numbers into questions about $\gcd$ of indices.

Pisano period

$F_n\mathrm{mod}m$ is periodic with period $\pi (m)$, the Pisano period.

Fact
$\pi (m)\le 6m$, with equality iff $m=2\cdot 5^k$
$\pi$ is multiplicative over coprime factors: $\pi (\mathrm{lcm})=\mathrm{lcm}(\pi (p_i^{e_i}))$
$\pi (p^k)=p^{k-1}\pi (p)$ (conjecturally always)
$\pi (10)=60$, $\pi (10^2)=300$, $\pi (10^3)=1500$
For $p\equiv \pm 1(\mathrm{mod}5)$: $\pi (p)\mid p-1$
For $p\equiv \pm 2(\mathrm{mod}5)$: $\pi (p)\mid 2(p+1)$

So $F_n\mathrm{mod}m$ for astronomically large $n$ reduces to $F_{n\mathrm{mod}\pi (m)}\mathrm{mod}m$ — though fast doubling usually makes that unnecessary.

Zeckendorf representation

Every positive integer has a unique representation as a sum of non-consecutive Fibonacci numbers.

Greedy: repeatedly subtract the largest Fibonacci number that fits. This gives a “Fibonacci base” that appears in:

• Wythoff’s game — the losing positions are $(\lfloor k\varphi \rfloor ,\lfloor k{\varphi }^2\rfloor )$;
• Fibonacci coding (a self-delimiting variable-length code);
• problems asking for a representation with no two adjacent terms.

Where Fibonacci shows up

Problem	Why
Count binary strings with no two adjacent 1s	$F_{n+2}$
Tile a $2\times n$ board with dominoes	$F_{n+1}$
Climbing stairs, 1 or 2 at a time	$F_{n+1}$
Number of subsets of $\{\mathrm{1..}n\}$ with no two consecutive	$F_{n+2}$
Worst case of the Euclidean algorithm	consecutive Fibonacci inputs
Golden section search	ratio $\varphi$
AVL tree minimum size at height $h$	Fibonacci-like
Wythoff’s game	Zeckendorf / $\varphi$

Generalisations

• Lucas numbers $L_n$: same recurrence, $L_0=2$, $L_1=1$. Related by $L_n=F_{n-1}+F_{n+1}$ and $F_{2n}=F_n{L}_n$.
• Tribonacci / $k$-bonacci: $O(k^3\log n)$ by matrix power, or $O(k\log k\log n)$ by Bostan-Mori.
• General linear recurrences: see Linear Recurrences.

See also: Linear Recurrences · Matrix Exponentiation · Euclidean Algorithm