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 .

The method used to compute F(n) is, however, based on the following identity: Let A be the two by two matrix . Observe that  Thus F(n) can be computed quickly (in time  instead of ) by computing  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.