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 0n1000 \le n \le 100
5818e3
Table of F10nF_{{10}^{n}} to 50 digits for 0n200 \le n \le 20

Symmetry

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

Recurrence relations

Consecutive terms

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

Distant terms

7ef2c7
Fn=2Fn2+Fn3F_{n} = 2 F_{n - 2} + F_{n - 3}
cbfe21
Fn=3Fn3+2Fn4F_{n} = 3 F_{n - 3} + 2 F_{n - 4}
5cb57e
Fn=Fm+1Fnm+FmFnm1F_{n} = F_{m + 1} F_{n - m} + F_{m} F_{n - m - 1}
a104b0
Fm+n=FmFn+1+Fm1FnF_{m + n} = F_{m} F_{n + 1} + F_{m - 1} F_{n}
70878b
Fm+n1=FmFn+Fm1Fn1F_{m + n - 1} = F_{m} F_{n} + F_{m - 1} F_{n - 1}

Doubling

35956b
F2n=Fn+12Fn12F_{2 n} = F_{n + 1}^{2} - F_{n - 1}^{2}
2ca869
F2n=(Fn+1+Fn1)FnF_{2 n} = \left(F_{n + 1} + F_{n - 1}\right) F_{n}
5745bd
F2n=Fn+22Fn+122Fn2F_{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+1Fn1(1)nF_{n}^{2} = F_{n + 1} F_{n - 1} - {\left(-1\right)}^{n}
ab563e
Fn2=Fn+mFnm+(1)n+mFm2F_{n}^{2} = F_{n + m} F_{n - m} + {\left(-1\right)}^{n + m} F_{m}^{2}
8db61e
Fn+iFn+jFnFn+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+1Fm+1Fn=(1)nFmnF_{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+12F_{n} = \left\lfloor \frac{{\varphi}^{n}}{\sqrt{5}} + \frac{1}{2} \right\rfloor
ad0d7a
Fn=φncos ⁣(πn)φn5F_{n} = \frac{{\varphi}^{n} - \cos\!\left(\pi n\right) {\varphi}^{-n}}{\sqrt{5}}

Matrix formulas

8a548e
(1110)n=(Fn+1FnFnFn1){\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)(FnFn1)\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+m1)=(1110)m(FnFn1)\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=0Fnzn=z1zz2\sum_{n=0}^{\infty} F_{n} {z}^{n} = \frac{z}{1 - z - {z}^{2}}
d0d91a
n=0Fnznn!=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=0n1(nk1k)F_{n} = \sum_{k=0}^{n - 1} {n - k - 1 \choose k}
d7c89c
Fn=k=0(n1)/2(nk1k)F_{n} = \sum_{k=0}^{\left\lfloor \left( n - 1 \right) / 2 \right\rfloor} {n - k - 1 \choose k}
b8ed8f
Fn=12n1k=0(n1)/25k(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=enucos ⁣(πn)enu5   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)+(1cos ⁣(π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=Un1 ⁣(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=in1Un1 ⁣(i2)F_{n} = {i}^{n - 1} U_{n - 1}\!\left(-\frac{i}{2}\right)

Hypergeometric functions

1c90fb
Fn=n2n12F1 ⁣(1n2,2n2,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 ⁣(1n2,2n2,1n,4)F_{n} = \,{}_2F_1\!\left(\frac{1 - n}{2}, \frac{2 - n}{2}, 1 - n, -4\right)

Finite sums

1eb5e7
k=0nFk=Fn+21\sum_{k=0}^{n} F_{k} = F_{n + 2} - 1
3bb7e4
k=0nF2k=F2n+11\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
FdFdnF_{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
pFp(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:nZ0})    (5x2+4Zor5x24Z)\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:kZandnFk}=#Z\# \left\{ k : k \in \mathbb{Z} \,\mathbin{\operatorname{and}}\, n \mid F_{k} \right\} = \# \mathbb{Z}
f5f706
Fn+60Fn(mod10)F_{n + 60} \equiv F_{n} \pmod {10}
9d26d2
{Fn:nZ0andFnZ}={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,  nF_{n} \sim \frac{{\varphi}^{n}}{\sqrt{5}}, \; n \to \infty
fdfdcc
limnFn+1Fn=φ\lim_{n \to \infty} \frac{F_{n + 1}}{F_{n}} = \varphi
d56025
limnFn+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>φn15F_{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=01F2n+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=512\sum_{n=1}^{\infty} \frac{{\left(-1\right)}^{n + 1}}{F_{n} F_{n + 1}} = \frac{\sqrt{5} - 1}{2}
da1873
n=01F2n+1=54θ22 ⁣(0,τ)   where τ=1πilog ⁣(352)\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=11Fn2=524(θ24 ⁣(0,τ)θ44 ⁣(0,τ)+1)   where τ=1πilog ⁣(352)\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=01F2n=752\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.

2019-11-11 15:50:15.016492 UTC