Fibonacci polynomials

From HandWiki

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]

[math]\displaystyle{ 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} }[/math]

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

[math]\displaystyle{ 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} }[/math]

They can be defined for negative indices by[3]

[math]\displaystyle{ F_{-n}(x)=(-1)^{n-1}F_{n}(x), }[/math]
[math]\displaystyle{ L_{-n}(x)=(-1)^nL_{n}(x). }[/math]

The Fibonacci polynomials form a sequence of orthogonal polynomials with [math]\displaystyle{ A_n=C_n=1 }[/math] and [math]\displaystyle{ B_n=0 }[/math].

Examples

The first few Fibonacci polynomials are:

[math]\displaystyle{ F_0(x)=0 \, }[/math]
[math]\displaystyle{ F_1(x)=1 \, }[/math]
[math]\displaystyle{ F_2(x)=x \, }[/math]
[math]\displaystyle{ F_3(x)=x^2+1 \, }[/math]
[math]\displaystyle{ F_4(x)=x^3+2x \, }[/math]
[math]\displaystyle{ F_5(x)=x^4+3x^2+1 \, }[/math]
[math]\displaystyle{ F_6(x)=x^5+4x^3+3x \, }[/math]

The first few Lucas polynomials are:

[math]\displaystyle{ L_0(x)=2 \, }[/math]
[math]\displaystyle{ L_1(x)=x \, }[/math]
[math]\displaystyle{ L_2(x)=x^2+2 \, }[/math]
[math]\displaystyle{ L_3(x)=x^3+3x \, }[/math]
[math]\displaystyle{ L_4(x)=x^4+4x^2+2 \, }[/math]
[math]\displaystyle{ L_5(x)=x^5+5x^3+5x \, }[/math]
[math]\displaystyle{ L_6(x)=x^6+6x^4+9x^2 + 2. \, }[/math]

Properties

  • The degree of Fn is n − 1 and the degree of Ln is n.
  • 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 ordinary generating functions for the sequences are:[4]
    [math]\displaystyle{ \sum_{n=0}^\infty F_n(x) t^n = \frac{t}{1-xt-t^2} }[/math]
    [math]\displaystyle{ \sum_{n=0}^\infty L_n(x) t^n = \frac{2-xt}{1-xt-t^2}. }[/math]
  • The polynomials can be expressed in terms of Lucas sequences as
    [math]\displaystyle{ F_n(x) = U_n(x,-1),\, }[/math]
    [math]\displaystyle{ L_n(x) = V_n(x,-1).\, }[/math]
  • They can also be expressed in terms of Chebyshev polynomials [math]\displaystyle{ \mathcal{T}_n(x) }[/math] and [math]\displaystyle{ \mathcal{U}_n(x) }[/math] as
    [math]\displaystyle{ F_n(x) = i^{n-1}\cdot\mathcal{U}_{n-1}(\tfrac{-ix}2),\, }[/math]
    [math]\displaystyle{ L_n(x) = 2\cdot i^n\cdot\mathcal{T}_n(\tfrac{-ix}2),\, }[/math]
where [math]\displaystyle{ i }[/math] is the imaginary unit.

Identities

Main page: Lucas sequence

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

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

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

[math]\displaystyle{ F_n(x)=\frac{\alpha(x)^n-\beta(x)^n}{\alpha(x)-\beta(x)},\,L_n(x)=\alpha(x)^n+\beta(x)^n, }[/math]

where

[math]\displaystyle{ \alpha(x)=\frac{x+\sqrt{x^2+4}}{2},\,\beta(x)=\frac{x-\sqrt{x^2+4}}{2} }[/math]

are the solutions (in t) of

[math]\displaystyle{ t^2-xt-1=0.\, }[/math]

For Lucas Polynomials n > 0, we have

[math]\displaystyle{ L_n(x)=\sum_{k=0}^{\lfloor n/2\rfloor} \frac{n}{n-k} \binom{n-k}{k} x^{n-2k}. }[/math]

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

[math]\displaystyle{ x^n=F_{n+1}(x)+\sum_{k=1}^{\lfloor n/2\rfloor}(-1)^k\left[\binom nk-\binom n{k-1}\right]F_{n+1-2k}(x). }[/math]

For example,

[math]\displaystyle{ x^4 = F_5(x)-3F_3(x)+2F_1(x)\, }[/math]
[math]\displaystyle{ x^5 = F_6(x)-4F_4(x)+5F_2(x)\, }[/math]
[math]\displaystyle{ x^6 = F_7(x)-5F_5(x)+9F_3(x)-5F_1(x)\, }[/math]
[math]\displaystyle{ x^7 = F_8(x)-6F_6(x)+14F_4(x)-14F_2(x)\, }[/math]

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 xk in Fn(x), namely

[math]\displaystyle{ F_n(x)=\sum_{k=0}^n F(n,k)x^k,\, }[/math]

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 [math]\displaystyle{ F(n, k)=\begin{cases}\displaystyle\binom{\frac12(n+k-1)}{k} &\text{if }n \not\equiv k \pmod 2,\\[12pt] 0 &\text{else}. \end{cases} }[/math]

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

References

  1. ↑ 1.0 1.1 Benjamin & Quinn p. 141
  2. ↑ Benjamin & Quinn p. 142
  3. ↑ 3.0 3.1 3.2 Springer
  4. ↑ Weisstein, Eric W.. "Fibonacci Polynomial". http://mathworld.wolfram.com/FibonacciPolynomial.html. 
  5. ↑ A proof starts from page 5 in Algebra Solutions Packet (no author).

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



Retrieved from "https://handwiki.org/wiki/index.php?title=Fibonacci_polynomials&oldid=3007448"