Fibonacci polynomial

In mathematics, the Fibonacci polynomials are a polynomial sequence which can be considered as a generalization of the Fibonacci numbers. The polynomials generated in a similar way from the Lucas numbers are called Lucas polynomials.

Definition

These Fibonacci polynomials are defined by a recurrence relation:[1]

F_n(x)= \begin{cases}

0, & \mbox{if } n = 0\\ 1, & \mbox{if } n = 1\\ x F_{n - 1}(x) + F_{n - 2}(x),& \mbox{if } n \geq 2 \end{cases}

The first few Fibonacci polynomials are:

F_0(x)=0 \,
F_1(x)=1 \,
F_2(x)=x \,
F_3(x)=x^2+1 \,
F_4(x)=x^3+2x \,
F_5(x)=x^4+3x^2+1 \,
F_6(x)=x^5+4x^3+3x \,

The Lucas polynomials use the same recurrence with different starting values:[2] L_n(x) = \begin{cases} 2, & \mbox{if } n = 0 \\ x, & \mbox{if } n = 1 \\ x L_{n - 1}(x) + L_{n - 2}(x), & \mbox{if } n \geq 2. \end{cases}

The first few Lucas polynomials are:

L_0(x)=2 \,
L_1(x)=x \,
L_2(x)=x^2+2 \,
L_3(x)=x^3+3x \,
L_4(x)=x^4+4x^2+2 \,
L_5(x)=x^5+5x^3+5x \,
L_6(x)=x^6+6x^4+9x^2 + 2. \,

The Fibonacci and Lucas numbers are recovered by evaluating the polynomials at x = 1; Pell numbers are recovered by evaluating Fn at x = 2. The degrees of Fn is n − 1 and the degree of Ln is n. The ordinary generating function for the sequences are:[3]

\sum_{n=0}^\infty F_n(x) t^n = \frac{t}{1-xt-t^2}.
\sum_{n=0}^\infty L_n(x) t^n = \frac{2-xt}{1-xt-t^2}.

The polynomials can be expressed in terms of Lucas sequences as

F_n(x) = U_n(x,-1),\,
L_n(x) = V_n(x,-1).\,

Identities

Main article: Lucas sequence

As particular cases of Lucas sequences, Fibonacci polynomials satisfy a number of identities.

First, they can be defined for negative indices by[4]

F_{-n}(x)=(-1)^{n-1}F_{n}(x),\,L_{-n}(x)=(-1)^nL_{n}(x).

Other identities include:[4]

F_{m+n}(x)=F_{m+1}(x)F_n(x)+F_m(x)F_{n-1}(x)\,
L_{m+n}(x)=L_m(x)L_n(x)-(-1)^nL_{m-n}(x)\,
F_{n+1}(x)F_{n-1}(x)- F_n(x)^2=(-1)^n\,
F_{2n}(x)=F_n(x)L_n(x).\,

Closed form expressions, similar to Binet's formula are:[4]

F_n(x)=\frac{\alpha(x)^n-\beta(x)^n}{\alpha(x)-\beta(x)},\,L_n(x)=\alpha(x)^n+\beta(x)^n,

where

\alpha(x)=\frac{x+\sqrt{x^2+4}}{2},\,\beta(x)=\frac{x-\sqrt{x^2+4}}{2}

are the solutions (in t) of

t^2-xt-1=0.\,

Combinatorial interpretation

If F(n,k) is the coefficient of xk in Fn(x), so

F_n(x)=\sum_{k=0}^n F(n,k)x^k,\,

then F(n,k) is the number of ways an n−1 by 1 rectangle can be tiled with 2 by 1 dominoes and 1 by 1 squares so that exactly k squares are used.[1] Equivalently, F(n,k) is the number of ways of writing n−1 as an ordered sum involving only 1 and 2, so that 1 is used exactly k times. For example F(6,3)=4 and 5 can be written in 4 ways, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, as a sum involving only 1 and 2 with 1 used 3 times. By counting the number of times 1 and 2 are both used in such a sum, it is evident that F(n,k) is equal to the binomial coefficient

F(n,k)=\binom{\tfrac{n+k-1}{2}}{k}

when n and k have opposite parity. This gives a way of reading the coefficients from Pascal's triangle as shown on the right.

References

  • MathWorld.

Further reading

External links

  • "On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
  • "On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.