Fungrim home page

Fibonacci numbers

Table of contents: Definitions - Tables - Symmetry - Recurrence relations - Algebraic formulas - Matrix formulas - Generating functions - Sum representations - Elementary functions - Chebyshev polynomials - Hypergeometric functions - Finite sums - Divisibility - Asymptotics and limits - Bounds and inequalities - Reciprocal series

Definitions

fe11ce
Symbol: Fibonacci — FnF_{n} — Fibonacci number
373aa1
Fn=A000045 ⁣(n)F_{n} = \text{A000045}\!\left(n\right)

Tables

b506ad
Table of FnF_{n} for 0≤n≤1000 \le n \le 100
5818e3
Table of F10nF_{{10}^{n}} to 50 digits for 0≤n≤200 \le n \le 20

Symmetry

ce6dd0
F−n=(−1)n+1FnF_{-n} = {\left(-1\right)}^{n + 1} F_{n}

Recurrence relations

Consecutive terms

22dc6e
Fn=Fn−1+Fn−2F_{n} = F_{n - 1} + F_{n - 2}
6d437c
Fn=Fn+2−Fn+1F_{n} = F_{n + 2} - F_{n + 1}
a8f2ac
Fn+1=Fn+Fn−1F_{n + 1} = F_{n} + F_{n - 1}
10165f
Fn+2=Fn+1+FnF_{n + 2} = F_{n + 1} + F_{n}

Distant terms

7ef2c7
Fn=2Fn−2+Fn−3F_{n} = 2 F_{n - 2} + F_{n - 3}
cbfe21
Fn=3Fn−3+2Fn−4F_{n} = 3 F_{n - 3} + 2 F_{n - 4}
5cb57e
Fn=Fm+1Fn−m+FmFn−m−1F_{n} = F_{m + 1} F_{n - m} + F_{m} F_{n - m - 1}
a104b0
Fm+n=FmFn+1+Fm−1FnF_{m + n} = F_{m} F_{n + 1} + F_{m - 1} F_{n}
70878b
Fm+n−1=FmFn+Fm−1Fn−1F_{m + n - 1} = F_{m} F_{n} + F_{m - 1} F_{n - 1}

Doubling

35956b
F2n=Fn+12−Fn−12F_{2 n} = F_{n + 1}^{2} - F_{n - 1}^{2}
2ca869
F2n=(Fn+1+Fn−1)FnF_{2 n} = \left(F_{n + 1} + F_{n - 1}\right) F_{n}
5745bd
F2n=Fn+22−Fn+12−2Fn2F_{2 n} = F_{n + 2}^{2} - F_{n + 1}^{2} - 2 F_{n}^{2}
fc4fd1
F2n+1=Fn+12+Fn2F_{2 n + 1} = F_{n + 1}^{2} + F_{n}^{2}

Cassini's identity and generalizations

073466
Fn2=Fn+1Fn−1−(−1)nF_{n}^{2} = F_{n + 1} F_{n - 1} - {\left(-1\right)}^{n}
ab563e
Fn2=Fn+mFn−m+(−1)n+mFm2F_{n}^{2} = F_{n + m} F_{n - m} + {\left(-1\right)}^{n + m} F_{m}^{2}
8db61e
Fn+iFn+j−FnFn+i+j=(−1)nFiFjF_{n + i} F_{n + j} - F_{n} F_{n + i + j} = {\left(-1\right)}^{n} F_{i} F_{j}
301081
FmFn+1−Fm+1Fn=(−1)nFm−nF_{m} F_{n + 1} - F_{m + 1} F_{n} = {\left(-1\right)}^{n} F_{m - n}

Algebraic formulas

24107d
Fn=φn−(−φ)−n5F_{n} = \frac{{\varphi}^{n} - {\left(-\varphi\right)}^{-n}}{\sqrt{5}}
050fdb
Fn=⌊φn5+12⌋F_{n} = \left\lfloor \frac{{\varphi}^{n}}{\sqrt{5}} + \frac{1}{2} \right\rfloor
ad0d7a
Fn=φn−cos⁡ ⁣(πn)φ−n5F_{n} = \frac{{\varphi}^{n} - \cos\!\left(\pi n\right) {\varphi}^{-n}}{\sqrt{5}}

Matrix formulas

8a548e
(1110)n=(Fn+1FnFnFn−1){\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}}^{n} = \begin{pmatrix} F_{n + 1} & F_{n} \\ F_{n} & F_{n - 1} \end{pmatrix}
0e2425
(Fn+1Fn)=(1110)(FnFn−1)\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}
3a9c67
(Fn+mFn+m−1)=(1110)m(FnFn−1)\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

05209f
∑n=0∞Fnzn=z1−z−z2\sum_{n=0}^{\infty} F_{n} {z}^{n} = \frac{z}{1 - z - {z}^{2}}
d0d91a
∑n=0∞Fnznn!=25ez/2sinh⁡ ⁣(52z)\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

9638c1
Fn=∑k=0n−1(n−k−1k)F_{n} = \sum_{k=0}^{n - 1} {n - k - 1 \choose k}
d7c89c
Fn=∑k=0⌊(n−1)/2⌋(n−k−1k)F_{n} = \sum_{k=0}^{\left\lfloor \left( n - 1 \right) / 2 \right\rfloor} {n - k - 1 \choose k}
b8ed8f
Fn=12n−1∑k=0⌊(n−1)/2⌋5k(n2k+1)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

12b336
Fn=enu−cos⁡ ⁣(πn)e−nu5   where u=log⁡(φ)F_{n} = \frac{{e}^{n u} - \cos\!\left(\pi n\right) {e}^{-n u}}{\sqrt{5}}\; \text{ where } u = \log(\varphi)
fd732d
Fn=25{sinh⁡ ⁣(nu),n evencosh⁡ ⁣(nu),n odd   where u=log⁡(φ)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)
bceed4
Fn=(1+cos⁡ ⁣(πn))sinh⁡ ⁣(nu)+(1−cos⁡ ⁣(πn))cosh⁡ ⁣(nu)5   where u=log⁡(φ)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)
c4d78a
Fn=25(−i)nsinh⁡ ⁣(n(log⁡(φ)+12πi))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

aadf90
F2n=Un−1 ⁣(32)F_{2 n} = U_{n - 1}\!\left(\frac{3}{2}\right)
223ce1
F2n+1=25T2n+1 ⁣(52)F_{2 n + 1} = \frac{2}{\sqrt{5}} T_{2 n + 1}\!\left(\frac{\sqrt{5}}{2}\right)
ae76a3
Fn=in−1Un−1 ⁣(−i2)F_{n} = {i}^{n - 1} U_{n - 1}\!\left(-\frac{i}{2}\right)

Hypergeometric functions

1c90fb
Fn=n2n−1 2F1 ⁣(1−n2,2−n2,32,5)F_{n} = \frac{n}{{2}^{n - 1}} \,{}_2F_1\!\left(\frac{1 - n}{2}, \frac{2 - n}{2}, \frac{3}{2}, 5\right)
90c290
Fn= 2F1 ⁣(1−n2,2−n2,1−n,−4)F_{n} = \,{}_2F_1\!\left(\frac{1 - n}{2}, \frac{2 - n}{2}, 1 - n, -4\right)

Finite sums

1eb5e7
∑k=0nFk=Fn+2−1\sum_{k=0}^{n} F_{k} = F_{n + 2} - 1
3bb7e4
∑k=0nF2k=F2n+1−1\sum_{k=0}^{n} F_{2 k} = F_{2 n + 1} - 1
5eb446
∑k=0nF2k+1=F2n+2\sum_{k=0}^{n} F_{2 k + 1} = F_{2 n + 2}
82373a
∑k=0nFk2=FnFn+1\sum_{k=0}^{n} F_{k}^{2} = F_{n} F_{n + 1}
ac4d13
∑k=0n(nk)Fk=F2n\sum_{k=0}^{n} {n \choose k} F_{k} = F_{2 n}
f95561
∑k=0n(−1)k+1(nk)Fk=Fn\sum_{k=0}^{n} {\left(-1\right)}^{k + 1} {n \choose k} F_{k} = F_{n}
d454a3
∑k=0n(nk)2kFk=F3n\sum_{k=0}^{n} {n \choose k} {2}^{k} F_{k} = F_{3 n}

Divisibility

4b3947
Fd∣FdnF_{d} \mid F_{d n}
7b0abf
gcd⁡ ⁣(Fn,Fn+1)=1\gcd\!\left(F_{n}, F_{n + 1}\right) = 1
aaa244
gcd⁡ ⁣(Fn,Fn+2)=1\gcd\!\left(F_{n}, F_{n + 2}\right) = 1
da45c0
gcd⁡ ⁣(Fm,Fn)=Fgcd⁡(m,n)\gcd\!\left(F_{m}, F_{n}\right) = F_{\gcd\left(m, n\right)}
6db705
p∣Fp−(p5)p \mid F_{p - \left( \frac{p}{5} \right)}
c84407
Fp≡(p5)(modp)F_{p} \equiv \left( \frac{p}{5} \right) \pmod {p}
a0206a
(x∈{Fn:n∈Z≥0})  ⟺  (5x2+4∈Z  or⁡  5x2−4∈Z)\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)
4ec333
#{k:k∈Z  and⁡  n∣Fk}=#Z\# \left\{ k : k \in \mathbb{Z} \;\mathbin{\operatorname{and}}\; n \mid F_{k} \right\} = \# \mathbb{Z}
f5f706
Fn+60≡Fn(mod10)F_{n + 60} \equiv F_{n} \pmod {10}
9d26d2
{Fn:n∈Z≥0  and⁡  Fn∈Z}={F0,F1,F2,F12}={0,1,144}\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

0574c1
Fn∼φn5,  n→∞F_{n} \sim \frac{{\varphi}^{n}}{\sqrt{5}}, \; n \to \infty
fdfdcc
lim⁡n→∞Fn+1Fn=φ\lim_{n \to \infty} \frac{F_{n + 1}}{F_{n}} = \varphi
d56025
lim⁡n→∞Fn+mFn=φm\lim_{n \to \infty} \frac{F_{n + m}}{F_{n}} = {\varphi}^{m}

Bounds and inequalities

f3aff5
Fn<φn+15F_{n} < \frac{{\varphi}^{n} + 1}{\sqrt{5}}
9c53d7
Fn>φn−15F_{n} > \frac{{\varphi}^{n} - 1}{\sqrt{5}}
412334
F2n<Fn+12<F2n+1F_{2 n} < F_{n + 1}^{2} < F_{2 n + 1}

Reciprocal series

ae9d30
∑n=0∞1F2n+1+1=52\sum_{n=0}^{\infty} \frac{1}{F_{2 n + 1} + 1} = \frac{\sqrt{5}}{2}
344963
∑n=1∞(−1)n+1FnFn+1=5−12\sum_{n=1}^{\infty} \frac{{\left(-1\right)}^{n + 1}}{F_{n} F_{n + 1}} = \frac{\sqrt{5} - 1}{2}
da1873
∑n=0∞1F2n+1=54θ22 ⁣(0,τ)   where τ=1πilog⁡ ⁣(3−52)\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)
22b67a
∑n=1∞1Fn2=524(θ24 ⁣(0,τ)−θ44 ⁣(0,τ)+1)   where τ=1πilog⁡ ⁣(3−52)\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)
6d8bf0
∑n=0∞1F2n=7−52\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