Recursive sequences and girard-waring identities with applications in sequence transformation

1.   Introduction

Albert Girard published a class of identities in Amsterdam in 1629. Edward Waring published similar material in Cambridge in 1762-1782, which are referred as Girard-Waring identities A000330 [15]. These identities may be derived from the earlier work of Sir Isaac Newton. Surveys and some applications of these identities can be found in Comtet [2] (P. 198), Gould [3], Shapiro and one of the authors [5], and the first two authors [7]. We now give a different approach to derive Girard-Waring identities by using the Binet formula A097600 [15] of recursive sequences and divided differences. Meanwhile, this approach offers some formulas and identities that may have wider applications.

This paper starts from an application of recursive sequences in the construction of a combinatorial identity referred to as generalized Girard-Waring identity from the Binet formula and the generating function of a recursive sequence. By using the generalized Girard-Waring identity, the Binet type Girard-Waring identity is derived, which yields the classical Girard-Waring identity by making use of divided differences. Many number and polynomial sequences can be defined, characterized, evaluated, and/or classified by linear recurrence relations with certain orders. A number sequence $\{ a_n\}$ is called sequence of order $2$ if it satisfies the linear recurrence relation of order $2$:

for constants $p, q\in{ {\mathbb R}}$ and $q\not = 0$ and initial conditions $a_0$ and $a_1$. Let $\alpha$ and $\beta$ be two roots of of quadratic equation $x^2-p x-q = 0.$ From He and Shiue [6], the general term of the sequence $\{a_{n}\}$ can be presented by the following Binet formula.

In the next section, from the above Binet formula we will construct a generalized Girard-Waring identity by using generating function of the recursive sequence shown in (1). Then the Binet type Girard-Waring identity will be derived accordingly. In Section 3, we present a way to construct classical Girard-Waring identity from the Binet type Girard-Waring identity by using the divided difference. Section 4 will give an application of the generalized Girard-Waring identity to the transformation of recursive sequences of numbers and polynomials.

2.   Construction of Binet type Girard-Waring identity by using recursive sequences

We now find the generating function of the sequence defined by (1).

Proposition 1. Denote $A(s) = \sum_{n\geq 0}a_{n}s^{n}$. Then

Furthermore, the Taylor expansion A165998 [15] of $A(s)$ is

Proof. From the definition of $A(s)$, we have

Hence, we obtain (3).

We now give the Taylor series expansion of the right-hand side of (3) as follows:

which completes the proof of the proposition.

Corollary 1. Let $(a_n)$ be the sequence defined by the recursive relation (1), and let $\alpha$ and $\beta$ be two distinct roots of the characteristic polynomial of (1). Then we have the following generalized Girard-Waring identity:

If $a_0 = 0$ and $a_1 = 1$, (4) implies the Binet type Girard-Waring identity

where $p = \alpha+\beta$ and $q = -\alpha\beta$.

Proof. From (4), we have

or equivalently, (4). Hence, we obtain the following identity for all recursive sequences defined by (1)

where $p = \alpha+\beta$ and $\alpha\beta = -q$, or equivalently,

If $a_{0} = 0$ and $a_{1} = 1$, from (4) we have

which implies the first equation of (5) by noting (2). Substituting $p = \alpha+\beta$ and $q = -\alpha\beta$ into the first equation of (5), we obtain the second equation of (5) and complete the proof.

Remark 1. He and Shapiro [5] used Riordan array approach to establish the Binet type Girard-Waring identity (5).

3.   Re-establishing of Girard-Waring identities by using the Binet type Girard-Waring identity

We now prove the classical Girard-Waring identity

by using the first equation of (5). First, we need the following lemmas.

Lemma 3.1. Let $n\in { {\mathbb N}}$. Then

Proof. From the Chu-Vandermonde formula and noting, the left-hand side of (8) can be written as

where on the first line

We split the inner sum of the rightmost hand of the above equation for the left-hand side of (8),

into two cases. For $i = 0$, we have the above sum to be $\frac{n}{n - 0 + 0} = \frac{n}{n} = 1$. For $i > 0$, we have

where the last sum is zero because it is the finite difference of a polynomial with its degree one less than the order of the difference. Hence, the left-hand side of (8) becomes

Lemma 3.2. Let $\alpha$ and $\beta$ be two roots of the characteristic polynomial of the recursive relation(1). Then

Proof. The left-hand side of (9) can be written as

where by using Lemma 3.1 the inner sum can be written as

Thus we obtain (9).

To prove Girard-Waring identity (7), we only need to mention that (9) implies

There are some alternative forms of formula (7). As an example, we give the following one. If $x+y+z = 0$, then (7) gives

which implies

Thus, when $n$ is even, we have formula

while for odd $n$ we have

where $x+y+z = 0$. Consequently, if $n = 3$, then

which was shown in He and Shiue [7]. Saul and Andreescu [14] have shown that the cube vanishes if $x = -(y+z)$. Note that Euler used this to solve the general cubic. In [7], the following proposition as an application of (12) was presented.

Proposition 2. Let $x, y\in{ {\mathbb N}}$. Then $pxy(x+y)|(x^p+y^p-(x+y)^p)$ when $p \geq 3$ is a prime.

4.   Application to transferring recursive sequences

As a source of Binet Girard-Waring identity, the generalized Girard-Waring identity (4) has many applications including a simple way in transferring recursive sequences of numbers and polynomials. For example, we consider Chebyshev polynomials of the first kind A028297 [15] defined by

for all $n\geq 2$ and $T_0(x) = 1$ and $T_1(x) = x$. Then from Corollary 1, we have

Similarly, for Lucas numbers A000032 [15] defined by

for all $n\geq 2$ and $L_0 = 2$ and $L_1 = 1$, we have

From the expressions of $T_n(x)$ and $L_n$, we may see that

or equivalently,

where $i = \sqrt{-1}$.

In general, we have the following result for transferring a certain class of recursive sequences to the Chebyshev polynomial sequence of the first kind at certain points.

Theorem 4.1. Let $\{ a_n\}_{n\geq 0}$ be a sequence defined by (1) with $pa_0 = 2a_1$, $a_0\not = 0$, and let $\{T_n(x)\}_{n\geq 0}$ be the Chebyshev polynomial sequence of the first kind defined by (13). Then

where

Namely, $a_n$ shown in (14) can be expressed as

Proof. From (14) we have

If $pa_0 = 2a_1$, then from (4), we have

Setting $a_n = C_nT_n(x_0)$ and using the latest forms of $T_n(x)$ and $a_n$, we obtain

which implies

for the value $x_0$ satisfying

Thus, we solve the last equation to get $x_0$ shown in (15). Substituting $x_0$ into (17) and solving for $C$ yields

By substituting $x_0$ shown in (15) into (14) and noting $2a_1 = pa_0$, we obtain (16).

Theorem 4.1 can be extended to recursive polynomial case.

Corollary 2. Let $\{ a_n(x)\}_{n\geq 0}$ be a recursive polynomial sequence defined by

for $n\geq 2$, where $p(x)\in { {\mathbb R}}[x]$ and $q\in{ {\mathbb R}}$, with initial conditions $a_0(x)$ and $a_1(x)$ satisfying $p(x)a_0(x) = 2a_1(x)$. Then

where $T_n(x)$ is the $n$th Chebyshev polynomial of the first kind.

Proof. The proof is similar as the proof of Theorem 4.1 and is omitted.

Example 4.1. For instance, consider the Lucas polynomial sequence $\{L_n(x)\}$ defined by

for all $n\geq 2$ with the initial conditions $L_0(x) = 2$ and $L_1(x) = x$. Thus

for all $n\geq 0$. In addition, the Lucas numbers $L_n = L_n(1)$ can be transferred to

for all $n\geq 0$.

Similarly, for the Pell-Lucas polynomials A122075 [15] $Q_n(x)$ defined by (see Horadam and Mahon [9])

for all $n\geq 2$ with initial conditions $Q_0(x) = 2$ and $Q_1(x) = 2x$, we have

for all $n\geq 0$. The first one of the above formulas is shown in Magnus, Oberhettinger, and Soni [12].

For the Dickson polynomials of the first kind $D_n(x)$ A000041 [15] defined by (see Lidl, Mullen, and Turnwald [11])

for all $n\geq 2$ with initial conditions $D_0(x) = 2$ and $D_1(x) = x$, where $a\in{ {\mathbb R}}$, we have

for all $n\geq 0$.

For the Viate polynomials of the second kind defined by (see Horadan [8])

for all $n\geq 2$ with the initial conditions $v_0(x) = 2$ and $v_1(x) = x$, we have

for all $n\geq 0$. The first one of the above formulas can be seen in Jacobsthal [10] and Robbins [13].

We now consider the recursive number or polynomial sequences defined by (1) with initial conditions $a_0 = 0$ and $a_1\not = 0$, where $p\in { {\mathbb R}}[x]$ and $q\in{ {\mathbb R}}$. For instance,

for all $n\geq 1$, where initial conditions are $\hat U_0 = 0$ and $\hat U_1 = 1$. It is obvious that $\hat U_{n+1} = U_n$, the Chebyshev polynomials of the second kind A135929 [15]. By using (4), we have

From (1) and initial conditions $a_0 = 0$ and $a_1 = 1$, we obtain

Comparing with the rightmost sides of (19) and (20), we have the following result.

Theorem 4.2. Let $\{ a_n\}_{n\geq 0}$ be the sequence defined by (1) with $a_0 = 0$ and $a_1\not = 0$, and let $\{U_n(x)\}_{n\geq 0}$ be the Chebyshev polynomial sequence of the second kind defined by (18). Then

where

Namely,

Proof. Let $a_n$ and $\hat U_n$ be the sequences shown in the rightmost of (20) and (19), respectively. Suppose $a_n = C_n\hat U_n(x_0)$ for some $x_0$. Then we may have

for $x_0 = \pm ip/(2\sqrt{q})$ and

which implies

Consequently, (21) follows.

Example 4.2. Among all the homogeneous linear recurring sequences satisfying second order homogeneous linear recurrence relation (1) with a nonzero $p$ and arbitrary initial conditions $\{ a_0, a_1\}$, the Lucas sequence with respect to $\{ p, q\}$ is defined in one of the authors paper [4], which is the sequence satisfying (1) with initial conditions $a_0 = 0$ and $a_1 = 1$. The relationships among the recursive sequences and the Chebyshev polynomial sequence of the second kind at certain points and some nonlinear expressions are studied. Theorem 4.2 presents the relationships of the Chebyshev polynomial sequence of the second kind at some points with a more general class of recursive sequences defined by (1) with initial conditions $a_0 = 0$ and $a_1\not = 0$. For instance, for the Fibonacci numbers $F_n$ A000045 [15] with respect to $\{ p, q\} = \{1, 1\}$ and initial conditions $a_0 = 0$ and $a_1 = 1$, we have

(see Aharonov, Beardon, and Driver [1]). For the Pell numbers $P_n$ A000129 [15] with respect to $\{ p, q\} = \{2, 1\}$ and initial conditions $a_0 = 0$ and $a_1 = 1$, we have

For the Jacobsthal numbers (cf. [2]) $J_n$ A001045 [15] with respect to $\{ p, q\} = \{1, 2\}$ and initial conditions $a_0 = 0$ and $a_1 = 1$, we have

For the numbers $A_n$ shown in the sequence of $n$ coin flips that win on the last flip A198834 [15] defined by the recurrence relation (1) with respect to $\{ p, q\} = \{1, 1\}$ and initial conditions $a_0 = 0$ and $a_1 = 2$, we have $\{A_n\} = \{ 0, 2, 2, 4, 6, 10, 16, \ldots\}$ and

For the numbers $B_n$ shown in the sequence of the numerators of the fractions in a 'zero-transform' approximation A163271 [15] defined by the recurrence relation (1) with respect to $\{ p, q\} = \{2, 1\}$ and initial conditions $a_0 = 0$ and $a_1 = 2$, we have $\{B_n\} = \{ 0, 2, 4, 10, 24, 58, \ldots\}$ and

Theorem 4.2 can be extended to recursive polynomial case as Chebyshev polynomials of the second kind.

Corollary 3. Let $\{a_n(x)\}_{n\geq 0}$ be the recursive polynomial sequence defined by

for $n\geq 2$, where $p(x)\in{ {\mathbb R}}[x]$ and $q\in{ {\mathbb R}}$, with initial conditions $a_0(x) = 0$ and $a_1(x)\not = 0$. Then

Proof. The result can be proved by using similar argument in the proof of Theorem 4.2.

Example 4.3. For instance, for Pell polynomials A122075 [15] defined by (see Horadam and Mahon [9])

for all $n\geq 2$ with initial conditions $P_0(x) = 0$ and $P_1(x) = 1$, we have

for all $n\geq 0$, where $U_{-1}(x) = 0$. The above formulas are shown in Magnus, Oberhettinger, and Soni [12].

Similarly, for Viate polynomials of the first kind defined by (see Horadan [8])

for all $n\geq 2$ with initial conditions $V_0(x) = 0$ and $V_1(x) = 1$, we have

for all $n\geq 0$. The first one of the above formulas is shown in Horadan [8]. From the above formulas and the similar formulas of $v_n(x)$ shown above, one may obtain

which are shown in Robins [13].

Gegenbauer-Humbert polynomial sequences, denoted by $\{ P^{\lambda, y, C}(x)\}$, is defined by the recurrence relation

for all $n\geq 2$ with initial conditions $P^{\lambda, y, C}_{0}(x) = C^{-\lambda}$ and $P^{\lambda, y, C}_{1}(x) = 2\lambda xC^{-\lambda -1}$. Particularly, for $\lambda = 1$, we denote $P^{\lambda, y, C}_{n}(x)$ by $P^{y, C}_{n}(x)$ and (23) becomes

for all $n\geq 2$ and $P^{y, C}_0(x) = C^{-1}$ and $P^{y, C}_1(x) = 2xC^{-2}$. From (4), we have the expression of $P^{y, C}_{n}(x)$ as

Thus,

are the Chebyshev polynomials of the second kind with the first few elements as $1, 2x, 4x^2-1, 8x^3-4x, \ldots$, and

are the Pell polynomials ([2]) with the first few elements as $1, 2x, 4x^2+1, 8x^3+4x, \ldots$.

Similar to Theorem 4.2, we may establish the following result.

Theorem 4.3. Let $P^{y, C}_n(x)$ and $P^{y'C'}_n(x)$ be two Gegenbauer-Humbert polynomials defined by (24) with respect two difference complex parameter pairs $(y, C)$ and $(y', C')$, respectively. Then

if the complex variables $x_1$ and $x_2$ satisfy

where

Proof. Let $P^{y, C}_n(x_1) = \alpha_n P^{y'C'}_n(x_2)$. Then from the rightmost side of (25) for $P^{y, C}_n(x)$ and $P^{y'C'}_n(x)$, respectively, we have

for

or equivalently, (28), and $\alpha_n$ satisfying

Consequently, we obtain

which completes the proof of the theorem.

Example 4.4. The Chebyshev polynomials of the second kind $P^{1, 1}_n(x_1)$ can be transferred to the Pell polynomials $P^{-1, 1}_n(x_2)$ by using

where $x_2^2 = -x_1^2$. More precisely, noticing (26) and using $x_2^2 = -x_1^2$ we may write the righthand side of the above equation as

where the last equation comes from (25).

Acknowledgments

The authors would like to express their sincere thanks to the editor and two referees for their comments.