# Fibonacci polynomials

The polynomials $U _ { n } ( x )$ (cf. [a1] and [a4]) given by

\begin{equation} \tag{a1} \left. \begin{cases} { U _ { 0 } ( x ) = 0, } \\ { U _ { 1 } ( x ) = 1, } \\ { U _ { n } ( x ) = x U _ { n - 1 } ( x ) + U _ { n - 2 } ( x ) , \quad n = 2,3, \dots . } \end{cases} \right. \end{equation}

They reduce to the Fibonacci numbers $F _ { n }$ for $x = 1$ and they satisfy several identities, which may be easily proved by induction, e.g.:

\begin{equation} \tag{a2} U _ { - n } ( x ) = ( - 1 ) ^ { n - 1 } U _ { n } ( x ); \end{equation}

\begin{equation} \tag{a3} U _ { m + n } ( x ) = U _ { m + 1 } ( x ) U _ { n } ( x ) + U _ { m } ( x ) U _ { n - 1 } ( x ); \end{equation}

\begin{equation} \tag{a4} U _ { n + 1 } ( x ) U _ { n - 1 } ( x ) - U _ { n } ^ { 2 } ( x ) = ( - 1 ) ^ { n } ; \end{equation}

\begin{equation} \tag{a5} U _ { n } ( x ) = \frac { \alpha ^ { n } ( x ) - \beta ^ { n } ( x ) } { \alpha ( x ) - \beta ( x ) }, \end{equation}

where

\begin{equation*} \alpha ( x ) = \frac { x + ( x ^ { 2 } + 4 ) ^ { 1 / 2 } } { 2 } , \beta ( x ) = \frac { x - ( x ^ { 2 } + 4 ) ^ { 1 / 2 } } { 2 }, \end{equation*}

so that $\alpha ( x ) \beta ( x ) = - 1$; and

\begin{equation} \tag{a6} U _ { n + 1 } ( x ) = \sum _ { j = 0 } ^ { [ n / 2 ] } \frac { ( n - j ) ! } { j ! ( n - 2 j ) ! } x ^ { n - 2 j } , n = 0,1, \dots , \end{equation}

where $[ y ]$ denotes the greatest integer in $y$.

W.A. Webb and E.A. Parberry [a14] showed that the $U _ { n } ( x )$ are irreducible polynomials over the ring of integers if and only if $n$ is a prime number (cf. also Irreducible polynomial). They also found that $x _ { j } = 2 i \operatorname { cos } ( j \pi / n )$, $j = 1 , \dots , n - 1$, are the $n - 1$ roots of $U _ { n } ( x )$ (see also [a2]). M. Bicknell [a1] proved that $U _ { m } ( x )$ divides $U _ { n } ( x )$ if and only if $m$ divides $n$. V.E. Hoggatt Jr., and C.T. Long [a3] introduced the bivariate Fibonacci polynomials $U _ { n } ( x , y )$ by the recursion

\begin{equation} \tag{a7} \left. \begin{cases}{ U _ { 0 } ( x , y ) = 0 ,}\\{ U _ { 1 } ( x , y ) = 1, }\\{ U _ { n } ( x , y ) = x U _ { n - 1 } ( x , y ) + y U _ { n - 2 } ( x , y ), }\\{ \quad n = 2 , 3 , \ldots ,}\end{cases} \right. \end{equation}

and they showed that the $U _ { n } ( x , y )$ are irreducible over the rational numbers if and only if $n$ is a prime number. They also generalized (a5) and proved that

\begin{equation} \tag{a8} U _ { n + 1 } ( x , y ) = \sum _ { j = 0 } ^ { [ n / 2 ] } \frac { ( n - j ) ! } { j ! ( n - 2 j ) ! } x ^ { n - 2 j } y ^ { j }, \end{equation}

\begin{equation*} n = 0,1 , \ldots \end{equation*}

In a series of papers, A.N. Philippou and his associates (cf. [a5], [a6], [a7], [a8], [a9], [a10], [a11], [a12], [a13]) introduced and studied Fibonacci, Fibonacci-type and multivariate Fibonacci polynomials of order $k$, and related them to probability and reliability. Let $k$ be a fixed positive integer greater than or equal to $2$. The Fibonacci polynomials of order $k$, $U _ { N } ^ { ( k ) } ( x )$, are defined by

\begin{equation} \tag{a9} \left\{ \begin{array}{l}{ U _ { 0 } ^ { ( k ) } ( x ) = 0, }\\{ U _ { 1 } ^ { ( k ) } ( x ) = 1, }\\{ U _ { n } ^ { ( k ) } ( x ) = \sum _ { j = 1 } ^ { n } x ^ { k - j } U _ { n - j } ^ { ( k ) } ( x ) , \quad n = 2 , \ldots , k, }\\{ U _ { n } ^ { ( k ) } ( x ) = \sum _ { j = 1 } ^ { k } x ^ { k - j } U _ { n - j } ^ { ( k ) } ( x ), }\\{ n = k + 1 , k + 2 , \ldots . }\end{array} \right. \end{equation}

For $k = 2$ these reduce to $U _ { n } ( x )$, and for $x = 1$ these reduce to $U _ { n } ^ { ( k ) }$, the Fibonacci numbers of order $k$ (cf. [a11]). Deriving and expanding the generating function of $U _ { N } ^ { ( k ) } ( x )$, they [a12] obtained the following generalization of (a6) in terms of the multinomial coefficients (cf. Multinomial coefficient):

\begin{equation} \tag{a10} U _ { n + 1 } ^ { ( k ) } ( x ) = \sum \frac { ( n _ { 1 } + \ldots + n _ { k } ) ! } { n _ { 1 } ! \ldots n _ { k } ! } x ^ { k ( n _ { 1 } + \ldots + n _ { k } ) - n }, \end{equation}

\begin{equation*} n = 0,1 , \ldots , \end{equation*}

where the sum is taken over all non-negative integers $n _ { 1 } , \ldots , n _ { k }$ such that $n _ { 1 } + 2 n _ { 2 } + \ldots + k n _ { k } = n$. They also obtained a simpler formula in terms of binomial coefficients. As a byproduct of (a10), they were able to relate these polynomials to the number of trials $N _ { k }$ until the occurrence of the $k$th consecutive success in independent trials with success probability $p$. For $p = 1 / 2$ this formula reduces to

\begin{equation} \tag{a11} \mathsf{P} ( N _ { k } = n + k ) = \frac { U _ { n + 1 } ^ { ( k ) } } { 2 ^ { n + k } } ,\, n = 0,1, \dots . \end{equation}

The Fibonacci-type polynomials of order $k$, $F _ { n } ^ { ( k ) } ( x )$, defined by (a12)

have simpler multinomial and binomial expansions than $U _ { N } ^ { ( k ) } ( x )$. The two families of polynomials are related by

\begin{equation} \tag{a13} U _ { n } ^ { ( k ) } ( x ) = x ^ { 1 - n } F _ { n } ^ { ( k ) } ( x ^ { k } ) ,\; n = 1,2 , \ldots . \end{equation}

Furthermore, with $q = 1 - p$,

\begin{equation} \tag{a14} \mathsf{P} ( N _ { k } = n ) = p ^ { n } F _ { n + 1 - k } ^ { ( k ) } \left( \frac { q } { p } \right) , \end{equation}

\begin{equation*} n = k , k + 1 , \dots . \end{equation*}

Assuming that the components of a consecutive $k$-out-of-$n$: $F$-system are ordered linearly and function independently with probability $p$, Philippou [a6] found that the reliability of the system, $R _ { l } ( p ; k , n )$, is given by

\begin{equation} \tag{a15} R_{l} ( p ; k , n ) = p ^ { - 1 } q ^ { n + 1 } F _ { n + 2 } \left( \frac { p } { q } \right), \end{equation}

\begin{equation*} n = k , k + 1 , \dots . \end{equation*}

If the components of the system are ordered circularly, then its reliability, $R _ { c } ( p ; k , n )$, is given by (cf. [a10])

\begin{equation} \tag{a16} R _ { c } ( p ; k , n ) = p q ^ { n - 1 } \sum _ { j = 1 } ^ { k } j F _ { n - j + 1 } ^ { ( k ) } ( \frac { p } { q } ), \end{equation}

\begin{equation*} n = k , k + 1 , \dots . \end{equation*}

Next, denote by $N _ { k , r }$ the number of independent trials with success probability $p$ until the occurrence of the $r$th $k$th consecutive success. It is well-known [a5] that $N _ { k , r }$ has the negative binomial distribution of order $k$ with parameters $r$ and $p$. Philippou and C. Georghiou [a9] have related this probability distribution to the $( r - 1 )$-fold convolution of $F _ { n } ^ { ( k ) } ( x )$ with itself, say $F _ { n , r } ^ { ( k ) } ( x )$, as follows: (a17)

\begin{equation*} n = k r , k r + 1 , \dots, \end{equation*}

which reduces to (a14) for $r = 1$, and they utilized effectively relation (a17) for deriving two useful expressions, a binomial and a recurrence one, for calculating the above probabilities.

Let $\mathbf x = ( x _ { 1 } , \dots , x _ { k } )$. The multivariate Fibonacci polynomials of order $k$ (cf. [a8]), $H _ { n } ^ { ( k ) } ( \mathbf{x} )$, are defined by the recurrence (a18)

For $\mathbf{x} = ( x ^ { k - 1 } , x ^ { k - 2 } , \dots , 1 )$, $H _ { n } ^ { ( k ) } ( \mathbf{x} ) = U _ { n } ^ { ( k ) } ( \mathbf{x} )$, $n = 0,1 , \dots$, and for $\mathbf{x} = ( x , \ldots , x )$, $H _ { n } ^ { ( k ) } ( \mathbf{x} ) = F _ { n } ^ { ( k ) } ( x )$. These polynomials have the following multinomial expansion:

\begin{equation} \tag{a19} H _ { n + 1 } ^ { ( k ) } ( x ) = \sum \frac { ( n _ { 1 } + \ldots + n _ { k } ) ! } { n _ { 1 } ! \ldots n _ { k } ! } x _ { 1 } ^ { n _ { 1 } } \ldots x _ { k } ^ { n _ { k } }, \end{equation}

\begin{equation*} n = 0,1 , \ldots , \end{equation*}

where the sum is taken over all non-negative integers $n _ { 1 } , \ldots , n _ { k }$ such that $n _ { 1 } + 2 n _ { 2 } + \ldots + k n _ { k } = n$. Let the random variable $X$ be distributed as a multi-parameter negative binomial distribution of order $k$ (cf. [a7]) with parameters $r , q_{ 1} , \dots , q _ { k }$ ($r > 0$, $0 < q _ { j } < 1$ for $j = 1 , \dots , k$ and $0 < q _ { 1 } + \ldots + q _ { k } < 1$). Philippou and D.L. Antzoulakos [a8] showed that the $( r - 1 )$-fold convolution, $H _ { n , r } ^ { ( k ) } ( \mathbf x )$, of $H _ { n } ^ { ( k ) } ( \mathbf{x} )$ with itself is related to this distribution by

\begin{equation} \tag{a20} \mathsf{P} ( X = n ) = p ^ { r } H _ { n + 1 , r } ^ { ( k ) } ( q _ { 1 } , \dots , q _ { k } ), \end{equation}

\begin{equation*} n = 0,1 , \ldots \end{equation*}

Furthermore, they have effectively utilized relation (a20) in deriving a recurrence for calculating the above probabilities.

How to Cite This Entry:
Fibonacci polynomials. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Fibonacci_polynomials&oldid=50630
This article was adapted from an original article by Andreas N. Philippou (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article