# Fibonacci numbers

Fibonacci numbers are the numbers in a sequence defined as follows:

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

The first several elements of the sequence (OEIS) are:

$$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...$$

## Properties

Fibonacci numbers possess a lot of interesting properties. Here are a few of them:

• Cassini's identity $$F_{n-1} F_{n+1} - F_n^2 = (-1)^n$$
• "Addition" rule $$F_{n+k} = F_k F_{n+1} + F_{k-1} F_n$$
• Applying the previous identity to the case of $n = k$, we get $$F_{2n} = F_n (F_{n+1} + F_{n-1})$$
• From this we can prove by induction that for any positive integer $k$ $$F_{nk} \equiv 0 (mod F_n)$$
• The inverse is also true: If $F_m \equiv 0 (mod F_n)$, then $m \equiv 0 (mod n)$
• GCD identity: $$GCD(F_m, F_n) = F_{GCD(m, n)}$$
• Fibonacci numbers are the worst possible inputs for Euclidean algorithm (see Lame's theorem in Euclidean algorithm)