The call fibonacci(n) computes the nth Fibonacci number F(n), if n is an integer; otherwise it returns unevaluated.

The call fibonacci(n, x) computes the nth Fibonacci polynomial in x if n is an integer; otherwise it returns unevaluated.

The Fibonacci numbers are defined by the linear recurrence

The Fibonacci polynomials are defined similarly by

Note that $F\left(n\right)=F\left(n\,1\right)$.

The method used to compute F(n) is, however, based on the following identity: Let A be the two by two matrix $\left[\left[1\,1\right]\,\left[1\,0\right]\right]$. Observe that $\left[F\left(n+1\right)\,F\left(n\right)\right]=A·\left[F\left(n\right)\,F\left(n-1\right)\right]$. Thus F(n) can be computed quickly (in time $\mathrm{O}\left({\log \left(n\right)}^3\right)$ instead of $\mathrm{O}\left(n^2\right)$) by computing $A^n$ using binary powering.

The generating function for F(n, x) is

The command with(combinat,fibonacci) allows the use of the abbreviated form of this command.

$\mathrm{with}\left(\mathrm{combinat}\,\mathrm{fibonacci}\right)\:$

$\mathrm{fibonacci}\left(5\right)$

$5$

$\mathrm{seq}\left(\mathrm{fibonacci}\left(i\right)\,i=0..10\right)$

$0,1,1,2,3,5,8,13,21,34,55$

$\mathrm{seq}\left(\mathrm{fibonacci}\left(i\right)\,i=-10..0\right)$

$\mathrm{-55},34,\mathrm{-21},13,\mathrm{-8},5,\mathrm{-3},2,\mathrm{-1},1,0$

$\mathrm{seq}\left(\mathrm{fibonacci}\left(i\,x\right)\,i=1..5\right)$

$1,x,x^2+1,x^3+2x,x^4+3x^2+1$

$\mathrm{fibonacci}\left(n\right)$

$\mathrm{fibonacci}\left(n\right)$