Fibonacci number ($F_n$)

The Fibonacci numbers satisfy $F_0=0$, $F_1=1$, and $F_{n+1}=F_n+F_{n-1}$.

For positive integers $m,n$, the Fibonacci numbers satisfy $F_m\mid F_{mn}$. The Fibonacci addition formula gives $F_{mn+m}=F_{m-1}{F}_{mn}+F_m{F}_{mn+1}$, so mathematical induction on $n$ proves the assertion. This explains why every fifth Fibonacci number is divisible by $F_5=5$.

Compute adjacent Fibonacci numbers together, starting at $(0,1)$ and applying $(a,b)\mapsto (b,a+b)$. The shared pair avoids repeating the same recursive subproblem and gives $n$ additions for $F_n$. This counts arithmetic operations; exact integers grow with $n$.

Consider a component that remembers its previous input $p$ and maps input $x$ to $x+p$, then sets $p:=x$. Feeding each output back into the same component gives state transition $(x,p)\mapsto (x+p,x)$. Starting at $(1,0)$, the successive outputs are $1,2,3,5,\dots$, the Fibonacci numbers $F_{k+1}$ after $k\ge 1$ calls. The state transition, rather than a memoryless function on one integer, explains the recurrence. Replacing the component between calls or repeatedly feeding a fixed external input gives different behavior.

The Pisano period $\pi (m)$ is the period of the Fibonacci number sequence in modular arithmetic modulo $m$, with $F_0=0$ and $F_1=1$. Consecutive residues evolve by the invertible update $(a,b)\mapsto (b,a+b)$ on a finite set, so the pair sequence returns to $(0,1)$ and is periodic from the start.

The Zeckendorf representation expresses a nonnegative integer as a sum of nonconsecutive Fibonacci numbers, using the sequence that starts $1,2,3,5,\dots$. Every nonnegative integer has exactly one such representation; repeatedly taking the largest available Fibonacci number constructs it.

Every positive integer is a unique sum of nonconsecutive Fibonacci numbers, using the sequence $1,2,3,5,8,\dots$ with one copy of $1$. The greedy procedure selects the largest allowable Fibonacci number and repeats on the remainder.

For the Fibonacci numbers $F_0=0$, $F_1=1$, the identity $F_{n+1}{F}_{n-1}-F_n^2=(-1{)}^n$ holds for $n\ge 1$. It follows by induction: replacing each term using the Fibonacci recurrence negates the left-hand side when $n$ increases by one, and the value at $n=1$ is $-1$.

The identities $F_{2k}=F_k(2F_{k+1}-F_k)$ and $F_{2k+1}=F_k^2+F_{k+1}^2$ compute $(F_n,F_{n+1})$ recursively from the pair at $\lfloor n/2\rfloor$. Recursion depth is $O(\log n)$, with a constant number of large integer operations per level; the bit cost still depends on operand length.

The vector $(F_{n+1},F_n{)}^T$ advances by multiplication by $A$. Matrix powers therefore prove modular recurrence identities uniformly in $n$. Explicitly, $A^3\equiv I(\mathrm{mod}2)$, $A^8\equiv I(\mathrm{mod}3)$, and $A^5\equiv 3I(\mathrm{mod}5)$. The last congruence gives $F_{n+5}\equiv 3F_n(\mathrm{mod}5)$, hence $5\mid F_{5j}$ for every nonnegative $j$.

With the standard Fibonacci numbers $F_0=0$, $F_1=1$, this identity holds for $n\ge 0$, $k\ge 1$. At $k=1$ it is immediate. If it holds for $k$ at every $n$, apply it at $n+1$ and use $F_{n+2}=F_{n+1}+F_n$ to obtain $F_{n+k+1}=F_{k+1}{F}_{n+1}+F_k{F}_n$, proving the assertion by mathematical induction. Taking $k=n$ gives $F_{2n}=F_n(F_{n+1}+F_{n-1})$ for $n\ge 1$, linking the doubling formula to the Lucas numbers.

Consecutive Fibonacci numbers are coprime by the Euclidean algorithm. The Fibonacci addition formula writes $F_m=F_{m-n}{F}_{n+1}+F_{m-n-1}{F}_n$ for $m>n$. Taking the greatest common divisor with $F_n$ removes the last summand, and multiplication by the coprime factor $F_{n+1}$ leaves that gcd unchanged. The case $m=n$ uses $F_0=0$. Applying the Euclidean algorithm to the indices yields the strong-divisibility identity $\gcd (F_m,F_n)=F_{\gcd (m,n)}$ for nonnegative indices, with the usual zero conventions.

For $\varphi =(1+\sqrt{5})/2$ and $\psi =(1-\sqrt{5})/2$, the Fibonacci numbers satisfy

For nonnegative $n,m,l$,Cassini's identity is the adjacent-index special case.

The linear recurrence relation defining the Fibonacci numbers, with $F_0=0$ and $F_1=1$. Its state $(F_{n+1},F_n{)}^T$ advances by the matrix $\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$, so matrix powers describe repeated updates.