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_{F\left(n\right)\,F\left(n-1\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)$

$-55\,34\,-21\,13\,-8\,5\,-3\,2\,-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{combinat:-fibonacci}\left(n\right)$