combinat - Maple Programming Help

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

$F\left(n\right)=F\left(n-1\right)+F\left(n-2\right)\mathrm{where}F\left(0\right)=0\mathrm{and}F\left(1\right)=1$

 • The Fibonacci polynomials are defined similarly by

$F\left(n,x\right)=xF\left(n-1,x\right)+F\left(n-2,x\right)\mathrm{where}F\left(0,x\right)=0\mathrm{and}F\left(1,x\right)=1$

 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({\mathrm{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

$\frac{t}{-{t}^{2}-tx+1}=\sum _{n=0}^{\mathrm{\infty }}F\left(n,x\right){t}^{n}$

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

Examples

 > $\mathrm{with}\left(\mathrm{combinat},\mathrm{fibonacci}\right):$
 > $\mathrm{fibonacci}\left(5\right)$
 ${5}$ (1)
 > $\mathrm{seq}\left(\mathrm{fibonacci}\left(i\right),i=0..10\right)$
 ${0}{,}{1}{,}{1}{,}{2}{,}{3}{,}{5}{,}{8}{,}{13}{,}{21}{,}{34}{,}{55}$ (2)
 > $\mathrm{seq}\left(\mathrm{fibonacci}\left(i\right),i=-10..0\right)$
 ${-}{55}{,}{34}{,}{-}{21}{,}{13}{,}{-}{8}{,}{5}{,}{-}{3}{,}{2}{,}{-}{1}{,}{1}{,}{0}$ (3)
 > $\mathrm{seq}\left(\mathrm{fibonacci}\left(i,x\right),i=1..5\right)$
 ${1}{,}{x}{,}{{x}}^{{2}}{+}{1}{,}{{x}}^{{3}}{+}{2}{}{x}{,}{{x}}^{{4}}{+}{3}{}{{x}}^{{2}}{+}{1}$ (4)
 > $\mathrm{fibonacci}\left(n\right)$
 ${\mathrm{combinat:-fibonacci}}{}\left({n}\right)$ (5)