Properties of Fibonacci Numbers

Theorem

Let $F_n$ denote the $n$th Fibonacci number:

The Fibonacci numbers are a sequence $\sequence {F_n}$ of integers which is formally defined recursively as:

$F_n = \begin {cases} 0 & : n = 0 \\ 1 & : n = 1 \\ F_{n - 1} + F_{n - 2} & : \text {otherwise} \end {cases}$

for all $n \in \Z_{\ge 0}$.

Fibonacci Number with Negative Index

$\forall n \in \Z_{> 0} : F_{-n} = \paren {-1}^{n + 1} F_n$

Euler-Binet Formula

The Fibonacci numbers have a closed-form solution:

$F_n = \dfrac {\phi^n - \paren {1 - \phi}^n} {\sqrt 5} = \dfrac {\phi^n - \paren {-1 / \phi}^n} {\sqrt 5} = \dfrac {\phi^n - \paren {-1}^n \phi^{-n} } {\sqrt 5} = \dfrac {\phi^n - \paren {1 - \phi}^n} {\phi - \paren {1 - \phi}}$

where $\phi$ is the golden mean.

Putting $\hat \phi = 1 - \phi = -\dfrac 1 \phi$ this can be written:

$F_n = \dfrac {\phi^n - \hat \phi^n} {\sqrt 5}$

From Definition 2 of Golden Mean: $\phi = \dfrac {1 + \sqrt 5} 2$

Therefore, substituting $\sqrt 5 = 2\phi - 1 = \phi - \paren {1 - \phi} = \phi - \hat \phi$, the above can be written as:

$F_n = \dfrac {\phi^n - \hat \phi^n} {\paren {\phi - \hat \phi}}$

Fibonacci Number as Sum of Binomial Coefficients

\(\ds \forall n \in \Z_{>0}: \, \)

\(\ds F_n\)

\(=\)

\(\ds \sum_{k \mathop = 0}^{\floor {\frac {n - 1} 2} } \dbinom {n - k - 1} k\)

\(\ds \)

\(=\)

\(\ds \binom {n - 1} 0 + \binom {n - 2} 1 + \binom {n - 3} 2 + \dotsb + \binom {n - j} {j - 1} + \binom {n - j - 1} j\)

where $j = \floor {\dfrac {n - 1} 2}$

Zeckendorf's Theorem

Every positive integer has a unique Zeckendorf representation.

That is: Let $n$ be a positive integer.

Then there exists a unique increasing sequence of integers $\left\langle{c_i}\right\rangle$ such that:

$\forall i \in \N: c_i \ge 2$

$c_{i + 1} > c_i + 1$

$\ds n = \sum_{i \mathop = 0}^k F_{c_i}$

where $F_m$ is the $m$th Fibonacci number.

For any given $n$, such a $\left\langle{c_i}\right\rangle$ is unique.

Sum of Non-Consecutive Fibonacci Numbers

Let $S$ be a non-empty set of distinct non-consecutive Fibonacci numbers not containing $F_0$ or $F_1$.

Let the largest element of $S$ be $F_j$.

Then:

$\ds \sum_{F_i \mathop \in S} F_i < F_{j + 1}$

That is, the sum of all the elements of $S$ is strictly less than the next largest Fibonacci number.

That is, given some increasing sequence $\sequence {c_i}$ satisfying $c_i \ge 2$ and $c_{i + 1} \ge c_i + 1$:

$\ds F_{c_k + 1} > \sum_{i \mathop = 0}^k F_{c_i}$

Sum of Sequence of Fibonacci Numbers

$\ds \forall n \in \Z_{\ge 0}: \sum_{j \mathop = 0}^n F_j = F_{n + 2} - 1$

Sum of Sequence of Even Index Fibonacci Numbers

\(\ds \forall n \ge 1: \, \)

\(\ds \sum_{j \mathop = 1}^n F_{2 j}\)

\(=\)

\(\ds F_2 + F_4 + F_6 + \cdots + F_{2 n}\)

\(\ds \)

\(=\)

\(\ds F_{2 n + 1} - 1\)

Sum of Sequence of Odd Index Fibonacci Numbers

\(\ds \forall n \ge 1: \, \)

\(\ds \sum_{j \mathop = 1}^n F_{2 j - 1}\)

\(=\)

\(\ds F_1 + F_3 + F_5 + \cdots + F_{2 n - 1}\)

\(\ds \)

\(=\)

\(\ds F_{2 n}\)

Sum of Odd Sequence of Products of Consecutive Fibonacci Numbers

$\ds \sum_{j \mathop = 1}^{2 n - 1} F_j F_{j + 1} = {F_{2 n} }^2$

Sum of Even Sequence of Products of Consecutive Fibonacci Numbers

$\ds \sum_{j \mathop = 1}^{2 n} F_j F_{j + 1} = {F_{2 n + 1} }^2 - 1$

Lucas Number as Sum of Fibonacci Numbers

Let $L_k$ be the $k$th Lucas number, defined as:

$L_n = \begin{cases}

2 & : n = 0 \\ 1 & : n = 1 \\ L_{n - 1} + L_{n - 2} & : \text{otherwise} \end{cases}$

Then:

$L_n = F_{n - 1} + F_{n + 1}$

Millin Series

The Millin series has the closed form expression:

$\ds \sum_{n \mathop = 0}^\infty \frac 1 {F_{2^n} } = \frac {7 - \sqrt 5} 2$

Recurrence Formula for Sum of Sequence of Fibonacci Numbers

Let $g_n$ be the sum of the first $n$ Fibonacci numbers.

Then:

$\forall n \ge 2: g_n = g_{n - 1} + g_{n - 2} + 1$

Cassini's Identity

$F_{n + 1} F_{n - 1} - F_n^2 = \paren {-1}^n$

Catalan's Identity

${F_n}^2 - F_{n - r} F_{n + r} = \left({-1}\right)^{n - r} {F_r}^2$

Vajda's Identity

Formulation 1

$F_{n + i} F_{n + j} - F_n F_{n + i + j} = \paren {-1}^n F_i F_j$

Formulation 2

$F_{n + k} F_{m - k} - F_n F_m = \left({-1}\right)^n F_{m - n - k} F_k$

d'Ocagne's Identity

$\forall m, n \in \Z: \paren {-1}^n F_{m - n} = F_m F_{n + 1} - F_n F_{n - 1}$

Honsberger's Identity

$\forall m, n \in \Z_{>0}: F_{m + n} = F_{m - 1} F_n + F_m F_{n + 1}$

Fibonacci Number in terms of Larger Fibonacci Numbers

$\forall m, n \in \Z_{>0} : \paren {-1}^n F_{m - n} = F_m F_{n - 1} - F_{m - 1} F_n$

Divisibility of Fibonacci Number

$\forall m, n \in \Z_{> 2} : m \divides n \iff F_m \divides F_n$

where $\divides$ denotes divisibility.

GCD of Fibonacci Numbers

$\forall m, n \in \Z_{> 2}: \gcd \set {F_m, F_n} = F_{\gcd \set {m, n} }$

where $\gcd \set {a, b}$ denotes the greatest common divisor of $a$ and $b$.