Fibonacci polynomials

Short description: Sequence of polynomials defined recursively

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:

$F_n(x)=\{\begin{array}{ll}0,& \text{if }n=0\\ 1,& \text{if }n=1\\ x{F}_{n-1}(x)+F_{n-2}(x),& \text{if }n\ge 2\end{array}$

The Lucas polynomials use the same recurrence with different starting values:

$L_n(x)=\{\begin{array}{ll}2,& \text{if }n=0\\ x,& \text{if }n=1\\ x{L}_{n-1}(x)+L_{n-2}(x),& \text{if }n\ge 2.\end{array}$

They can be defined for negative indices by

$F_{-n}(x)=(-1{)}^{n-1}{F}_n(x),$

$L_{-n}(x)=(-1{)}^n{L}_n(x).$

The Fibonacci polynomials form a sequence of orthogonal polynomials with $A_n=C_n=1$ and $B_n=0$.

Examples

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

Properties

• The degree of F_n is n − 1 and the degree of L_n is n.

• The Fibonacci and Lucas numbers are recovered by evaluating the polynomials at x = 1; Pell numbers are recovered by evaluating F_n at x = 2.

• The ordinary generating functions for the sequences are:

  $\sum _{n=0}^{\mathrm{\infty }}{F}_n(x)t^n=\frac{t}{1-xt-t^2}$

  $\sum _{n=0}^{\mathrm{\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).$

• They can also be expressed in terms of Chebyshev polynomials ${{𝒯}}_n(x)$ and ${{𝒰}}_n(x)$ as

  $F_n(x)=i^{n-1}\cdot {{𝒰}}_{n-1}(\frac{-ix}{2}),$

  $L_n(x)=2\cdot i^n\cdot {{𝒯}}_n(\frac{-ix}{2}),$

where $i$ is the imaginary unit.

Identities

Main article: Lucas sequence

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

$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{)}^n{L}_{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:

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

For Lucas Polynomials n > 0, we have

$L_n(x)=\sum _{k=0}^{\lfloor n/2\rfloor }\frac{n}{n-k}(\genfrac{}{}{0ex}{}{n-k}{k})x^{n-2k}.$

A relationship between the Fibonacci polynomials and the standard basis polynomials is given by

$x^n=F_{n+1}(x)+\sum _{k=1}^{\lfloor n/2\rfloor }(-1{)}^k[(\genfrac{}{}{0ex}{}{n}{k})-(\genfrac{}{}{0ex}{}{n}{k-1})]F_{n+1-2k}(x).$

For example,

$x^4=F_5(x)-3F_3(x)+2F_1(x)$

$x^5=F_6(x)-4F_4(x)+5F_2(x)$

$x^6=F_7(x)-5F_5(x)+9F_3(x)-5F_1(x)$

$x^7=F_8(x)-6F_6(x)+14F_4(x)-14F_2(x)$

Combinatorial interpretation

The coefficients of the Fibonacci polynomials can be read off from a left-justified Pascal's triangle following the diagonals (shown in red). The sums of the coefficients are the Fibonacci numbers.

If F(n,k) is the coefficient of x^k in F_n(x), namely

$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. 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)=\{\begin{array}{ll}(\genfrac{}{}{0ex}{}{\frac{1}{2}(n+k-1)}{k})& \text{if }n\equiv ̸k(\mathrm{mod}2),\\ 0& \text{else}.\end{array}$

This gives a way of reading the coefficients from Pascal's triangle as shown on the right.

References

• Benjamin, Arthur T.; Quinn, Jennifer J. (2003). "Fibonacci and Lucas Polynomial". Proofs that Really Count: The Art of Combinatorial Proof. Dolciani Mathematical Expositions. 27. Mathematical Association of America. p. 141. ISBN 978-0-88385-333-7. 
• Hazewinkel, Michiel, ed. (2001), "Fibonacci polynomials", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=Fibonacci_polynomials&oldid=14185 
• Hazewinkel, Michiel, ed. (2001), "Lucas polynomials", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=Lucas_polynomials&oldid=17297 
• Weisstein, Eric W.. "Lucas Polynomial". http://mathworld.wolfram.com/LucasPolynomial.html. 
• Jin, Z. On the Lucas polynomials and some of their new identities. Advances in Differential Equations 2018, 126 (2018). https://doi.org/10.1186/s13662-018-1527-9

Further reading

• Hoggatt, V. E.; Bicknell, Marjorie (1973). "Roots of Fibonacci polynomials.". Fibonacci Quarterly 11: 271–274. ISSN 0015-0517. 
• Hoggatt, V. E.; Long, Calvin T. (1974). "Divisibility properties of generalized Fibonacci Polynomials". Fibonacci Quarterly 12: 113. 
• Ricci, Paolo Emilio (1995). "Generalized Lucas polynomials and Fibonacci polynomials". Rivista di Matematica della Università di Parma. V. Ser. 4: 137–146. 
• Yuan, Yi; Zhang, Wenpeng (2002). "Some identities involving the Fibonacci Polynomials". Fibonacci Quarterly 40 (4): 314. 
• Cigler, Johann (2003). "q-Fibonacci polynomials". Fibonacci Quarterly (41): 31–40. 

External links

• OEIS sequence A162515 (Triangle of coefficients of polynomials defined by Binet form)
• OEIS sequence A011973 (Triangle of coefficients of Fibonacci polynomials)