Fibonacci

The nth Fibonacci number, with $F_0 = 0$ and $F_1 = 1$, extended to negative n by the same recurrence.

✓ checked against that system · ! checked, with disagreements (hover a chip)WikipediaFibonacci sequence↗Fibonacci number↗MathWorldFibonacciNumber↗WikidataQ47577↗Britannicatopic/Fibonacci-number↗DLMF26.11.p4↗FungrimFibonacci✓↗Fungrim entryOEISA000045↗Wolfram LanguageFibonacci✓↗Rosetta CodeFibonacci sequence↗

Fibonacci(n)the nth Fibonacci number $F_n$.

SageMathfibonacci(n)✓↗SymPyfibonacci(n)↗mpmathfib(n)Oscarfibonacci(n)JuliaBigInt(fibonacci(ZZ(n)))

Fibonacci(nu)a real (non-integer) index via Binet's formula, $F_\nu = \frac{\varphi^\nu - \cos(\pi\nu)\varphi^{-\nu}}{\sqrt5}$.

SageMathfibonacci(nu)✓↗SymPyfibonacci(nu)↗mpmathfib(nu)Oscarfibonacci(nu)JuliaBigInt(fibonacci(ZZ(nu)))

Fibonacci(n, x)the Fibonacci polynomial $F_n(x)$, from $F_n(x) = xF_{n-1}(x) + F_{n-2}(x)$, exact for a nonnegative integer n and numeric via the two-variable Binet formula for a real order.

SymPyfibonacci(n, x)↗

Typed signatures

Type	Package	Applies
(integer) -> integer	compute-engine	always
(number, any?) -> any	number-theoryreplaces compute-engine	always
(value) -> value	adelesreplaces number-theory	on ProfiniteNumber

Domain: Sequences

Details

• Defined by the recurrence $F_n = F_{n-1} + F_{n-2}$ with $F_0 = 0$, $F_1 = 1$.
• Closed form (Binet's formula): $F_n = \frac{\varphi^n - \psi^n}{\sqrt5}$, where $\varphi = \frac{1+\sqrt5}{2}$ and $\psi = \frac{1-\sqrt5}{2}$.
• Consecutive ratios $F_{n+1}/F_n$ converge to the golden ratio $\varphi$. See LucasL.
• GCD identity: $\gcd(F_m, F_n) = F_{\gcd(m,n)}$.
• Extends to negative n via $F_{-n} = (-1)^{n+1} F_n$.
• A list of indices is threaded over element-wise; a real (non-integer) index evaluates numerically via Binet's formula, and a symbolic second argument gives the Fibonacci polynomial.

Examples

Basic #

live ↗

In$\mathrm{Fibonacci}(0)$Out$0$

live ↗

In$\mathrm{Fibonacci}(1)$Out$1$

live ↗

In$\mathrm{Fibonacci}(10)$Out$55$

live ↗

In$\mathrm{Fibonacci}(20)$Out$6\,765$

live ↗

In$\mathrm{Fibonacci}(8)$Out$21$

Scope #

Exact at any size: $F_{100}$ has 21 digits

live ↗

In$\mathrm{Fibonacci}(100)$Out$354\,224\,848\,179\,261\,915\,075$

A real index uses $F_\nu = \frac{\varphi^\nu - \cos(\pi\nu)\,\varphi^{-\nu}}{\sqrt5}$

live ↗

In$\mathrm{Fibonacci}(1.5)$Out$0.920\,442\,065\,259\,926$

The two-argument Fibonacci polynomial $F_7(x)$, from $F_n(x) = x F_{n-1}(x) + F_{n-2}(x)$

live ↗

In$\mathrm{Fibonacci}(7, x)$Out$x^6+5x^4+6x^2+1$

The Fibonacci polynomial at a real order and argument, via the two-variable Binet formula

live ↗

In$\mathrm{Fibonacci}(5.8, 3)$Out$283.482\,730\,832\,949\,9$

Special value of the Fibonacci polynomial: $F_1(0) = 1$

live ↗

In$\mathrm{Fibonacci}(1, 0)$Out$1$

Special value of the Fibonacci polynomial: $F_0(0) = 0$

live ↗

In$\mathrm{Fibonacci}(0, 0)$Out$0$

$F_3(x) = x^2 + 1$ threads element-wise over a matrix argument

live ↗

In$\mathrm{Fibonacci}(3, \bigl\lbrack\bigl\lbrack-1, 0\bigr\rbrack, \bigl\lbrack0, 5\bigr\rbrack\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack2, 1\bigr\rbrack, \bigl\lbrack1, 26\bigr\rbrack\bigr\rbrack$

Threads element-wise over a list, as Wolfram's Listable heads do

live ↗

In$\mathrm{Fibonacci}(\bigl\lbrack1, 2, 3, 4\bigr\rbrack)$Out$\bigl\lbrack1, 1, 2, 3\bigr\rbrack$

A fully symbolic order stays exact -- the two-variable Binet formula, with $\pi$, $\cos$ and $\sqrt{x^2+4}$ left symbolic rather than rounded to a float (Wolfram's FunctionExpand[Fibonacci[n, x]] gives the same closed form)

live ↗

In$\mathrm{Fibonacci}(n, x)$Out$\frac{(\frac{1}{2}(x+(x^2+4)^{1/2}))^{n}-\frac{\cos(πn)}{((x+(x^2+4)^{1/2})/2)^{n}}}{\sqrt{x^2+4}}$

$F_{1/2}(x)$ at an exact half-integer order: $\cos(\pi/2) = 0$ vanishes exactly, leaving a bare radical -- not a 25-digit decimal approximation of $\pi$ (Wolfram's FunctionExpand[Fibonacci[1/2, x]] agrees)

live ↗

In$\mathrm{Fibonacci}(\frac{1}{2}, x)$Out$\frac{\sqrt{2}\sqrt{x+\sqrt{x^2+4}}}{2\sqrt{x^2+4}}$

Fractional index evaluated to 50 digits

live ↗

In$N(\mathrm{Fibonacci}(\frac{15}{17}), 50)$Out$0.956\,519\,913\,924\,311\,225\,085\,822\,634\,276\,922\,986\,486\,069\,690\,120\,61$

A Fibonacci polynomial at a complex point gives a Gaussian integer

live ↗

In$N(\mathrm{Fibonacci}(5, 8-i))$Out$3\,903.0-2\,064.0i$

Closed form of the Fibonacci polynomial in terms of $\sqrt{x^2+4}$

live ↗

In$\mathrm{FunctionExpand}(\mathrm{Fibonacci}(n, x))$Out$\frac{(\frac{1}{2}(x+(x^2+4)^{1/2}))^{n}-\frac{\cos(πn)}{((x+(x^2+4)^{1/2})/2)^{n}}}{\sqrt{x^2+4}}$

A half-integer index reduces to a square-root form

live ↗

In$\mathrm{FunctionExpand}(\mathrm{Fibonacci}(\frac{1}{2}, x))$Out$\frac{\sqrt{2}\sqrt{x+\sqrt{x^2+4}}}{2\sqrt{x^2+4}}$

Even index gives an odd polynomial in $x$

live ↗

In$\mathrm{Fibonacci}(2, -x)=-\mathrm{Fibonacci}(2, x)$Out$\mathrm{True}$

Odd index gives an even polynomial in $x$

live ↗

In$\mathrm{Fibonacci}(1, -x)=\mathrm{Fibonacci}(1, x)$Out$\mathrm{True}$

Threads over a list of indices

live ↗

In$\mathrm{Fibonacci}(\bigl\lbrack1, 2, 3, 4, 5\bigr\rbrack)$Out$\bigl\lbrack1, 1, 2, 3, 5\bigr\rbrack$

Generating function is $x/(1-x-x^2)$

live ↗

In$\mathrm{GeneratingFunction}(\mathrm{Fibonacci}(n), n, x)$Out$\frac{x}{-x^2-x+1}$

Commutes with complex conjugation

live ↗

In$\mathrm{Fibonacci}(1, \overline{z})=\overline{\mathrm{Fibonacci}(1, z)}$Out$\mathrm{True}$

Applied to a diagonal matrix, acts on each eigenvalue

live ↗

In$\mathrm{MatrixFunction}(\operatorname{\_1}↦\mathrm{Fibonacci}(3, \operatorname{\_1}), \bigl\lbrack\bigl\lbrack-1, 0\bigr\rbrack, \bigl\lbrack0, 5\bigr\rbrack\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack2, 0\bigr\rbrack, \bigl\lbrack0, 26\bigr\rbrack\bigr\rbrack$

Applications #

Consecutive ratios $F_{n+1}/F_n$ converge to the golden ratio $\varphi \approx 1.618$. See LucasL

live ↗

In$\frac{\mathrm{Fibonacci}(20)}{\mathrm{Fibonacci}(19)}$Out$\frac{6\,765}{4\,181}$

Properties #

$\sum_{k=1}^{n} F_k = F_{n+2} - 1$, here $F_{12} - 1 = 143$

live ↗

In$\sum_{k=1}^{10}\mathrm{Fibonacci}(k)$Out$143$

The doubling identity $F_{2n} = F_n L_n$. See LucasL

live ↗

In$\mathrm{Fibonacci}(20)=\mathrm{Fibonacci}(10)\mathrm{LucasL}(10)$Out$\mathrm{True}$

The defining recurrence $F_{10} = F_9 + F_8$

live ↗

In$\mathrm{Fibonacci}(10)=\mathrm{Fibonacci}(9)+\mathrm{Fibonacci}(8)$Out$\mathrm{True}$

Cassini's identity $F_{n-1}F_{n+1} - F_n^2 = (-1)^n$, here at $n = 6$

live ↗

In$\mathrm{Fibonacci}(5)\mathrm{Fibonacci}(7)-\mathrm{Fibonacci}(6)^2$Out$1$

$\gcd(F_{12}, F_{18}) = F_{\gcd(12, 18)}$

live ↗

In$\gcd(\mathrm{Fibonacci}(12), \mathrm{Fibonacci}(18))=\mathrm{Fibonacci}(\gcd(12, 18))$Out$\mathrm{True}$

Negative indices are supported via $F_{-n} = (-1)^{n+1} F_n$

live ↗

In$\mathrm{Fibonacci}(-5)$Out$5$

$F_2=1$

live ↗

In$\mathrm{Fibonacci}(2)$Out$1$

Known value · Wolfram MathematicalFunctionData, Fibonacci

$F_3=2$

live ↗

In$\mathrm{Fibonacci}(3)$Out$2$

Known value · Wolfram MathematicalFunctionData, Fibonacci

$F_4=3$

live ↗

In$\mathrm{Fibonacci}(4)$Out$3$

Known value · Wolfram MathematicalFunctionData, Fibonacci

$F_5=5$

live ↗

In$\mathrm{Fibonacci}(5)$Out$5$

Known value · Wolfram MathematicalFunctionData, Fibonacci

$F_6=8$

live ↗

In$\mathrm{Fibonacci}(6)$Out$8$

Known value · Wolfram MathematicalFunctionData, Fibonacci

$F_7=13$

live ↗

In$\mathrm{Fibonacci}(7)$Out$13$

Known value · Wolfram MathematicalFunctionData, Fibonacci

$F_9=34$

live ↗

In$\mathrm{Fibonacci}(9)$Out$34$

Known value · Wolfram MathematicalFunctionData, Fibonacci

Negative index reflects: $F_{-n}=(-1)^{n+1}F_n$, so $F_{-1}=1$

live ↗

In$\mathrm{Fibonacci}(-1)$Out$1$

Known value · Wolfram MathematicalFunctionData, Fibonacci

live ↗

In$\mathrm{Fibonacci}(1)\mathrm{Fibonacci}(3)-\mathrm{Fibonacci}(2)^2$Out$1$

Known value · Wolfram MathematicalFunctionData, Fibonacci, Cassini's formula

live ↗

In$\mathrm{Fibonacci}(2)^2-\mathrm{Fibonacci}(0)\mathrm{Fibonacci}(4)$Out$1$

Known value · Wolfram MathematicalFunctionData, Fibonacci, Catalan's identity

live ↗

In$\mathrm{Fibonacci}(2)\mathrm{Fibonacci}(3)\mathrm{Fibonacci}(4)\mathrm{Fibonacci}(6)\mathrm{Fibonacci}(7)\mathrm{Fibonacci}(8)+\mathrm{LucasL}(5)^2$Out$13\,225$

Known value · Wolfram MathematicalFunctionData, Fibonacci, Morgado identity

live ↗

In$\mathrm{Fibonacci}(0)\mathrm{Fibonacci}(1)\mathrm{Fibonacci}(3)\mathrm{Fibonacci}(4)$Out$0$

Known value · Wolfram MathematicalFunctionData, Fibonacci, Gelin‐Cesàro identity

Neat examples #

$F_{1000}$ has 209 digits. See IntegerDigits

live ↗

In$\mathrm{Length}(\mathrm{IntegerDigits}(\mathrm{Fibonacci}(1\,000)))$Out$209$

They grow fast: $F_{50}$ already exceeds twelve billion

live ↗

In$\mathrm{Fibonacci}(50)$Out$12\,586\,269\,025$

About

Examples	46
Checked against	Wolfram Language 46 agreeSageMath 28 agree3 errorSymPy 39 agree2 unevaluated2 errormpmath 28 agreemathlib4 11 agree2 errorOscar 11 agree3 errorJulia 27 agree2 error
Crosswalk	Wikipedia ×2MathWorldWikidataBritannicaDLMFFungrimFungrim entry ×40OEISWolfram LanguageSageMathSymPy ×2mpmathOscarJuliaRosetta Code

Implementation

mappedwolframpackages/oracle/src/mappings.ts

Julia's bare fibonacci(::Int) overflows past F(92); Nemo's ZZ makes it arbitrary-precision, and the BigInt conversion keeps the result a type Julia's own big() and arithmetic still know (other templates wrap operands in big(...)), unlike the bare ZZRingElem.

mappedsympypackages/oracle/src/mappings.ts

Julia's bare fibonacci(::Int) overflows past F(92); Nemo's ZZ makes it arbitrary-precision, and the BigInt conversion keeps the result a type Julia's own big() and arithmetic still know (other templates wrap operands in big(...)), unlike the bare ZZRingElem.

mappedsagepackages/oracle/src/mappings.ts

Julia's bare fibonacci(::Int) overflows past F(92); Nemo's ZZ makes it arbitrary-precision, and the BigInt conversion keeps the result a type Julia's own big() and arithmetic still know (other templates wrap operands in big(...)), unlike the bare ZZRingElem.

mappedoscarpackages/oracle/src/mappings.ts

Julia's bare fibonacci(::Int) overflows past F(92); Nemo's ZZ makes it arbitrary-precision, and the BigInt conversion keeps the result a type Julia's own big() and arithmetic still know (other templates wrap operands in big(...)), unlike the bare ZZRingElem.

mappedjuliapackages/oracle/src/mappings.ts

Julia's bare fibonacci(::Int) overflows past F(92); Nemo's ZZ makes it arbitrary-precision, and the BigInt conversion keeps the result a type Julia's own big() and arithmetic still know (other templates wrap operands in big(...)), unlike the bare ZZRingElem.

mappedmathlib4packages/oracle/src/mappings.ts

Julia's bare fibonacci(::Int) overflows past F(92); Nemo's ZZ makes it arbitrary-precision, and the BigInt conversion keeps the result a type Julia's own big() and arithmetic still know (other templates wrap operands in big(...)), unlike the bare ZZRingElem.

mappedsympypackages/oracle/src/mappings.ts

mappedmpmathpackages/oracle/src/mappings.ts

See also: LucasL