•
|
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.
|