compute Fibonacci numbers or polynomials - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Group Theory : Numbers : Integer Functions : combinat/fibonacci

combinat[fibonacci] - compute Fibonacci numbers or polynomials

Calling Sequence

fibonacci(n)

fibonacci(n, x)

Parameters

n, x

-

algebraic expressions

Description

• 

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

Fn=Fn1+Fn2whereF0=0andF1=1

• 

The Fibonacci polynomials are defined similarly by

Fn,x=xFn1,x+Fn2,xwhereF0,x=0andF1,x=1

  

Note that Fn=Fn,1.

• 

The method used to compute F(n) is, however, based on the following identity: Let A be the two by two matrix 1,1,1,0. Observe that Fn+1,Fn=AFn,Fn1 Thus F(n) can be computed quickly (in time Ologn3 instead of On2) by computing An using binary powering.

• 

The generating function for F(n, x) is

tt2tx+1=n=0Fn,xtn

• 

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

Examples

withcombinat,fibonacci:

fibonacci5

5

(1)

seqfibonaccii,i=0..10

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

(2)

seqfibonaccii,i=10..0

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

(3)

seqfibonaccii,x,i=1..5

1,x,x2+1,x3+2x,x4+3x2+1

(4)

fibonaccin

combinat:-fibonaccin

(5)

See Also

combinat


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam