Properties of Fibonacci Numbers

From ProofWiki
Jump to navigation Jump to search

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} = \left({-1}\right)^{n + 1} F_n$


Euler-Binet Formula

The Fibonacci numbers have a closed-form solution:

$F_n = \dfrac {\phi^n - \left({1 - \phi}\right)^n} {\sqrt 5} = \dfrac {\phi^n - \left({-1 / \phi}\right)^n} {\sqrt 5} = \dfrac {\phi^n - \left({-1}\right)^n\phi^{-n} } {\sqrt 5}$

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}$


Fibonacci Number as Sum of Binomial Coefficients

\(\, \displaystyle \forall n \in \Z_{>0}: \, \) \(\displaystyle F_n\) \(=\) \(\displaystyle \sum_{k \mathop = 0}^{\floor {\frac {n - 1} 2} } \dbinom {n - k - 1} k\)
\(\displaystyle \) \(=\) \(\displaystyle \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 {\frac {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$
$\displaystyle 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:

$\displaystyle \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 $\left\langle {c_i}\right\rangle$ satisfying $c_i \ge 2$ and $c_{i + 1} \ge c_i + 1$:

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


Sum of Sequence of Fibonacci Numbers

$\displaystyle \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

\(\, \displaystyle \forall n \ge 1: \, \) \(\displaystyle \sum_{j \mathop = 1}^n F_{2 j}\) \(=\) \(\displaystyle F_2 + F_4 + F_6 + \cdots + F_{2 n}\)
\(\displaystyle \) \(=\) \(\displaystyle F_{2 n + 1} - 1\)


Sum of Sequence of Odd Index Fibonacci Numbers

\(\, \displaystyle \forall n \ge 1: \, \) \(\displaystyle \sum_{j \mathop = 1}^n F_{2 j - 1}\) \(=\) \(\displaystyle F_1 + F_3 + F_5 + \cdots + F_{2 n - 1}\)
\(\displaystyle \) \(=\) \(\displaystyle F_{2 n}\)


Sum of Odd Sequence of Products of Consecutive Fibonacci Numbers

$\displaystyle \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

$\displaystyle \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 is the series defined as:

$\displaystyle \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} = \left({-1}\right)^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$


Fibonacci Number in terms of Smaller Fibonacci Numbers

$\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} : F_{m - n} = \left({-1}\right)^{n + 1} F_{m - 1} F_n + \left({-1}\right)^n F_m F_{n - 1}$


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$.