# Fibonacci numbers

## Definitions

Symbol: Fibonacci $F_{n}$ Fibonacci number
$F_{n} = \text{A000045}\!\left(n\right)$

## Tables

Table of $F_{n}$ for $0 \le n \le 100$
Table of $F_{{10}^{n}}$ to 50 digits for $0 \le n \le 20$

## Symmetry

$F_{-n} = {\left(-1\right)}^{n + 1} F_{n}$

## Recurrence relations

### Consecutive terms

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

### Distant terms

$F_{n} = 2 F_{n - 2} + F_{n - 3}$
$F_{n} = 3 F_{n - 3} + 2 F_{n - 4}$
$F_{n} = F_{m + 1} F_{n - m} + F_{m} F_{n - m - 1}$
$F_{m + n} = F_{m} F_{n + 1} + F_{m - 1} F_{n}$
$F_{m + n - 1} = F_{m} F_{n} + F_{m - 1} F_{n - 1}$

### Doubling

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

### Cassini's identity and generalizations

$F_{n}^{2} = F_{n + 1} F_{n - 1} - {\left(-1\right)}^{n}$
$F_{n}^{2} = F_{n + m} F_{n - m} + {\left(-1\right)}^{n + m} F_{m}^{2}$
$F_{n + i} F_{n + j} - F_{n} F_{n + i + j} = {\left(-1\right)}^{n} F_{i} F_{j}$
$F_{m} F_{n + 1} - F_{m + 1} F_{n} = {\left(-1\right)}^{n} F_{m - n}$

## Algebraic formulas

$F_{n} = \frac{{\varphi}^{n} - {\left(-\varphi\right)}^{-n}}{\sqrt{5}}$
$F_{n} = \left\lfloor \frac{{\varphi}^{n}}{\sqrt{5}} + \frac{1}{2} \right\rfloor$
$F_{n} = \frac{{\varphi}^{n} - \cos\!\left(\pi n\right) {\varphi}^{-n}}{\sqrt{5}}$

## Matrix formulas

${\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}}^{n} = \begin{pmatrix} F_{n + 1} & F_{n} \\ F_{n} & F_{n - 1} \end{pmatrix}$
$\begin{pmatrix} F_{n + 1} \\ F_{n} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n} \\ F_{n - 1} \end{pmatrix}$
$\begin{pmatrix} F_{n + m} \\ F_{n + m - 1} \end{pmatrix} = {\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}}^{m} \begin{pmatrix} F_{n} \\ F_{n - 1} \end{pmatrix}$

## Generating functions

$\sum_{n=0}^{\infty} F_{n} {z}^{n} = \frac{z}{1 - z - {z}^{2}}$
$\sum_{n=0}^{\infty} F_{n} \frac{{z}^{n}}{n !} = \frac{2}{\sqrt{5}} {e}^{z / 2} \sinh\!\left(\frac{\sqrt{5}}{2} z\right)$

## Sum representations

$F_{n} = \sum_{k=0}^{n - 1} {n - k - 1 \choose k}$
$F_{n} = \sum_{k=0}^{\left\lfloor \left( n - 1 \right) / 2 \right\rfloor} {n - k - 1 \choose k}$
$F_{n} = \frac{1}{{2}^{n - 1}} \sum_{k=0}^{\left\lfloor \left( n - 1 \right) / 2 \right\rfloor} {5}^{k} {n \choose 2 k + 1}$

## Elementary functions

$F_{n} = \frac{{e}^{n u} - \cos\!\left(\pi n\right) {e}^{-n u}}{\sqrt{5}}\; \text{ where } u = \log(\varphi)$
$F_{n} = \frac{2}{\sqrt{5}} \begin{cases} \sinh\!\left(n u\right), & n \text{ even}\\\cosh\!\left(n u\right), & n \text{ odd}\\ \end{cases}\; \text{ where } u = \log(\varphi)$
$F_{n} = \frac{\left(1 + \cos\!\left(\pi n\right)\right) \sinh\!\left(n u\right) + \left(1 - \cos\!\left(\pi n\right)\right) \cosh\!\left(n u\right)}{\sqrt{5}}\; \text{ where } u = \log(\varphi)$
$F_{n} = \frac{2}{\sqrt{5}} {\left(-i\right)}^{n} \sinh\!\left(n \left(\log(\varphi) + \frac{1}{2} \pi i\right)\right)$

## Chebyshev polynomials

$F_{2 n} = U_{n - 1}\!\left(\frac{3}{2}\right)$
$F_{2 n + 1} = \frac{2}{\sqrt{5}} T_{2 n + 1}\!\left(\frac{\sqrt{5}}{2}\right)$
$F_{n} = {i}^{n - 1} U_{n - 1}\!\left(-\frac{i}{2}\right)$

## Hypergeometric functions

$F_{n} = \frac{n}{{2}^{n - 1}} \,{}_2F_1\!\left(\frac{1 - n}{2}, \frac{2 - n}{2}, \frac{3}{2}, 5\right)$
$F_{n} = \,{}_2F_1\!\left(\frac{1 - n}{2}, \frac{2 - n}{2}, 1 - n, -4\right)$

## Finite sums

$\sum_{k=0}^{n} F_{k} = F_{n + 2} - 1$
$\sum_{k=0}^{n} F_{2 k} = F_{2 n + 1} - 1$
$\sum_{k=0}^{n} F_{2 k + 1} = F_{2 n + 2}$
$\sum_{k=0}^{n} F_{k}^{2} = F_{n} F_{n + 1}$
$\sum_{k=0}^{n} {n \choose k} F_{k} = F_{2 n}$
$\sum_{k=0}^{n} {\left(-1\right)}^{k + 1} {n \choose k} F_{k} = F_{n}$
$\sum_{k=0}^{n} {n \choose k} {2}^{k} F_{k} = F_{3 n}$

## Divisibility

$F_{d} \mid F_{d n}$
$\gcd\!\left(F_{n}, F_{n + 1}\right) = 1$
$\gcd\!\left(F_{n}, F_{n + 2}\right) = 1$
$\gcd\!\left(F_{m}, F_{n}\right) = F_{\gcd\left(m, n\right)}$
$p \mid F_{p - \left( \frac{p}{5} \right)}$
$F_{p} \equiv \left( \frac{p}{5} \right) \pmod {p}$
$\left(x \in \left\{ F_{n} : n \in \mathbb{Z}_{\ge 0} \right\}\right) \iff \left(\sqrt{5 {x}^{2} + 4} \in \mathbb{Z} \;\mathbin{\operatorname{or}}\; \sqrt{5 {x}^{2} - 4} \in \mathbb{Z}\right)$
$\# \left\{ k : k \in \mathbb{Z} \;\mathbin{\operatorname{and}}\; n \mid F_{k} \right\} = \# \mathbb{Z}$
$F_{n + 60} \equiv F_{n} \pmod {10}$
$\left\{ F_{n} : n \in \mathbb{Z}_{\ge 0} \;\mathbin{\operatorname{and}}\; \sqrt{F_{n}} \in \mathbb{Z} \right\} = \left\{F_{0}, F_{1}, F_{2}, F_{12}\right\} = \left\{0, 1, 144\right\}$

## Asymptotics and limits

$F_{n} \sim \frac{{\varphi}^{n}}{\sqrt{5}}, \; n \to \infty$
$\lim_{n \to \infty} \frac{F_{n + 1}}{F_{n}} = \varphi$
$\lim_{n \to \infty} \frac{F_{n + m}}{F_{n}} = {\varphi}^{m}$

## Bounds and inequalities

$F_{n} < \frac{{\varphi}^{n} + 1}{\sqrt{5}}$
$F_{n} > \frac{{\varphi}^{n} - 1}{\sqrt{5}}$
$F_{2 n} < F_{n + 1}^{2} < F_{2 n + 1}$

## Reciprocal series

$\sum_{n=0}^{\infty} \frac{1}{F_{2 n + 1} + 1} = \frac{\sqrt{5}}{2}$
$\sum_{n=1}^{\infty} \frac{{\left(-1\right)}^{n + 1}}{F_{n} F_{n + 1}} = \frac{\sqrt{5} - 1}{2}$
$\sum_{n=0}^{\infty} \frac{1}{F_{2 n + 1}} = \frac{\sqrt{5}}{4} \theta_{2}^{2}\!\left(0, \tau\right)\; \text{ where } \tau = \frac{1}{\pi i} \log\!\left(\frac{3 - \sqrt{5}}{2}\right)$
$\sum_{n=1}^{\infty} \frac{1}{F_{n}^{2}} = \frac{5}{24} \left(\theta_{2}^{4}\!\left(0, \tau\right) - \theta_{4}^{4}\!\left(0, \tau\right) + 1\right)\; \text{ where } \tau = \frac{1}{\pi i} \log\!\left(\frac{3 - \sqrt{5}}{2}\right)$
$\sum_{n=0}^{\infty} \frac{1}{F_{{2}^{n}}} = \frac{7 - \sqrt{5}}{2}$

Copyright (C) Fredrik Johansson and contributors. Fungrim is provided under the MIT license. The source code is on GitHub.

2021-03-15 19:12:00.328586 UTC