Alternating Sums in the Hosoya Polynomial Triangle

Rigoberto Flórez

Department of Mathematics and Computer Science

The Citadel Charleston, SC 29409 USA

          rigo.florez@citadel.edu

Robinson A. Higuita Instituto de Matemáticas Universidad de Antioquia Medellín Colombia

            robinharra@yahoo.es

Antara Mukherjee

Department of Mathematics and Computer Science

The Citadel Charleston, SC 29409 USA

       antara.mukherjee@citadel.edu

Abstract

The Hosoya polynomial triangle is a triangular arrangement of polynomials where each entry is a product of two polynomials. The geometry of this triangle is a good tool to study the algebraic properties of polynomial products. In particular, we find closed formulas for the alternating sum of products of polynomials such as Fibonacci polynomials, Chebyshev polynomials, Morgan-Voyce polynomials, Lucas polynomials, Pell polynomials, Fermat polynomials, Jacobsthal polynomials, and other familiar sequences of polynomials.

1 Introduction

The generalized Fibonacci polynomial is a recursive sequence that generalizes the Fibonacci numbers. The Hosoya triangle [6, 11, 12] consists of a triangular array of numbers where each of its entries is a product of two Fibonacci numbers (see Table 5). If in this triangle instead of Fibonacci numbers we put generalized Fibonacci polynomials, then we obtain the Hosoya polynomial triangle (see Table 3). The new triangle provides a good geometry to study algebraic and combinatorial properties of products of recursive sequences of polynomials. Here we use the Hosoya polynomial triangle to analyze the behavior of alternating sums of products of generalized Fibonacci polynomials. In particular, we analyze alternating sums of products of Fibonacci, Lucas, and other well-known sequences of polynomials.

Some known examples of generalized Fibonacci polynomials are the Fibonacci polynomials, Chebyshev polynomials, Morgan-Voyce polynomials, Lucas polynomials, Pell polynomials, Jacobsthal polynomials, and Fermat polynomials. Since the entries of the Hosoya polynomial triangle are products of two generalized Fibonacci polynomials, the triangle varies depending on the type of polynomials that its entries have (see Tables 2, 3, and 4 ). All these polynomials also have representations using Binet formulas.

In this paper we find two closed formulas for the alternating sum of the entries in the nth row of the Hosoya polynomial triangle. There are two Binet formulas for generalized Fibonacci polynomials, depending on the Binet representation of each polynomial we obtain a formula for its alternating sum. For instance, if we consider that the entries of the nth row of the Hosoya polynomial triangle to be products of Fibonacci numbers (see Table 5), then

F_{n}F_{1} − F_{n−1}F_{2} + F_{n−1}F_{2} − ⋯ + F_{1}F_{n} = F_{n+1}.

Evaluating the alternating sums found here, at integers, we obtain several well-known sequences (see Table 7). Those sequences can be found, for example, in Sloane [16].

2 Preliminaries and examples

In this section we give some examples, introduce notation, and some definitions that are going to be used throughout the paper. Some of them are well-known; however we prefer to restate them here as it will avoid ambiguities.

2.1 Generalized Fibonacci polynomials and generalized Hosoya polynomials

In the literature there are several definitions of generalized Fibonacci polynomials. However, the definition that we introduce here is simpler and covers other definitions. The generalized Fibonacci polynomial sequence is defined by the recurrence relation

G_{0}(x) = p_{0}(x), G_{1}(x) = p_{1}(x), and G_{n}(x) = d(x)G_{n−1}(x) + g(x)G_{n−2}(x) for n ≥ 2 (1)

where p_{0}(x), p_{1}(x), d(x), and g(x) are polynomials in ℤ[x].

For example, if we take p_{0}(x) = 1, p_{1}(x) = x, d(x) = x, and g(x) = 1 we obtain the regular Fibonacci polynomial sequence. That is, the Fibonacci polynomial sequence F_{n}(x), is defined by the recurrence relation

F_{0}(x) = 1, F_{1}(x) = x, and F_{n} = xF_{n−1}(x) + F_{n−2}(x) for n ≥ 2.

Letting x = 1 and choosing the correct values for p_{0}(x), p_{1}(x), d(x), and g(x), the generalized Fibonacci polynomial sequence gives rise to three classical numerical sequences, the Fibonacci sequence, the Lucas sequence, and the generalized Fibonacci sequence.

In Table 1 there are more familiar examples of generalized Fibonacci polynomials (see [9, 10, 12]). Hoggatt and Bicknell-Johnson [7] show that Schechter polynomials are another example of generalized Fibonacci polynomials.

We now give a formal definition of some of those polynomials. The Chebyshev polynomials T_{n}(x) of the first kind are a set of orthogonal polynomials defined as the solutions to the Chebyshev differential equations. This polynomial can be defined as the contour integral where the contour encloses the origin and is traversed in a counterclockwise direction,

T_{n}(x) = \frac{1}{4πi} ∮ \frac{(1 − t^{2})t^{−n−1}}{1 − 2tz + t^{2}} dt.

The Chebyshev polynomials of the first kind satisfy the recurrence relation given in the generalized Fibonacci polynomial sequence. Indeed,

T_{0}(x) = 1, T_{1}(x) = x, and T_{n}(x) = 2xT_{n−1}(x) − T_{n−2}(x) for n ≥ 2.

For instance,

T_{2}(x) = 2x^{2} − 1; T_{3}(x) = 4x^{3} − 3x; T_{4}(x) = 8x^{4} − 8x^{2} + 1; T_{5}(x) = 16x^{5} − 20x^{3} + 5x.

Morgan-Voyce [14] introduced two type of polynomial sequences. Here we use one of them and we also use a generalized version of the Morgan-Voyce polynomials given by André-Jeannin [2, 3, 4]. We note that Morgan-Voyce polynomials are well known in the study of electrical networks ([12, pp. 480–495] and [13, 14, 15]). The Morgan-Voyce polynomials are defined recursively as

\begin{matrix}B_{n}(x) = (x + 2)B_{n−1}(x) − B_{n−2}(x) \\ C_{n}(x) = (x + 2)C_{n−1}(x) − C_{n−2}(x) \end{matrix}

for n ≥ 2, where B_{0}(x) = 1, C_{0}(x) = 2, B_{1}(x) = C_{1}(x) = x + 2. For example,

\begin{matrix}B_{2}(x) = x^{2} + 4x + 3; & B_{3}(x) = x^{3} + 6x^{2} + 10x + 4; & B_{4}(x) = x^{4} + 8x^{3} + 21x^{2} + 20x + 5, \\ C_{2}(x) = x^{2} + 4x + 2; & C_{3}(x) = x^{3} + 6x^{2} + 9x + 2; & C_{4}(x) = x^{4} + 8x^{3} + 20x^{2} + 16x + 2. \end{matrix}

Polynomial  Initial value Initial value Recursive Formula
G_{0}(x) = p_{0}(x) G_{1}(x) = p_{1}(x) G_{n}(x) = d(x)G_{n−1}(x) + g(x)G_{n−2}(x)
Fibonacci  1  x  F_{n}(x) = xF_{n−1}(x) + F_{n−2}(x)
Lucas  2  x  D_{n}(x) = xD_{n−1}(x) + D_{n−2}(x)
Pell  1  2x  P_{n}(x) = 2xP_{n−1}(x) + P_{n−2}(x)
Pell-Lucas  2  2x  Q_{n}(x) = 2xQ_{n−1}(x) + Q_{n−2}(x)
Fermat  1  3x  Φ_{n}(x) = 3xΦ_{n−1}(x) − 2Φ_{n−2}(x)
Fermat-Lucas  2  3x  ϑ_{n}(x) = 3xϑ_{n−1}(x) − 2ϑ_{n−2}(x)
Chebyshev first kind  1  x  T_{n}(x) = 2xT_{n−1}(x) − T_{n−2}(x)
Chebyshev second kind 1  2x  U_{n}(x) = 2xU_{n−1}(x) − U_{n−2}(x)
Jacobsthal  1  1  J_{n}(x) = J_{n−1}(x) + 2xJ_{n−2}(x)
Jacobsthal-Lucas  2  1  j_{n}(x) = j_{n−1}(x) + 2xj_{n−2}(x)
Morgan-Voyce  1  x + 2  B_{n}(x) = (x + 2)B_{n−1}(x) − B_{n−2}(x)
Morgan-Voyce  2  x + 2  C_{n}(x) = (x + 2)C_{n−1}(x) − C_{n−2}(x)

Table 1: Recurrence relation of some generalized Fibonacci polynomials.

2.2 Hosoya polynomials and the Hosoya polynomial triangle

We now give a precise definition of both the Hosoya polynomial sequence and the Hosoya polynomial triangle. The Hosoya polynomial sequence {H(r, k)}_{r,k≥0} is defined using the double recursion

H(r, k) = δ(x)H(r − 1, k) + γ(x)H(r − 2, k)

and

H(r, k) = δ(x)H(r − 1, k − 1) + γ(x)H(r − 2, k − 2)

with initial conditions

H(0, 0) = p_{0}(x)^{2}; H(1, 0) = p_{0}(x)p_{1}(x); H(1, 1) = p_{0}(x)p_{1}(x); H(2, 1) = p_{1}(x)^{2},

where r > 1 and 0 ≤ k ≤ r − 1, and δ(x), γ(x), p_{0}(x), and p_{1}(x) are polynomials in ℤ[x]. This sequence gives rise to the Hosoya polynomial triangle, where the entry in position k (taken from left to right) of the rth row is equal to H(r, k) (see Table 2).

Proposition 1 is a generalization of [12, (15.4), p. 188] and [5, Proposition 1]. The proof of Proposition 1 has some similarities to the proof of [5, Proposition 1] which was done for integers. In Proposition 1 we prove that Table 2 is equal to Table 3. Here it is worth mentioning that in Table 3, for brevity, we use the notation G_{k} instead of G_{k}(x). We are

H(0, 0)
H(1, 0)  H(1, 1)
H(2, 0)  H(2, 1)  H(2, 2)
H(3, 0)  H(3, 1)  H(3, 2)  H(3, 3)
H(4, 0)  H(4, 1)  H(4, 2)  H(4, 3)  H(4, 4)
H(5, 0)  H(5, 1)  H(5, 2)  H(5, 3)  H(5, 4)  H(5, 5)

Table 2: Hosoya polynomial triangle.

\begin{aligned}& & & & G_{0} G_{0} \\ & & & G_{0} G_{1} & & G_{1} G_{0} \\ & & G_{0} G_{2} & & G_{1} G_{1} & & G_{2} G_{0} \\ & G_{0} G_{3} & & G_{1} G_{2} & & G_{2} G_{1} & & G_{3} G_{0} \\ G_{0} G_{4} & & G_{1} G_{3} & & G_{2} G_{2} & & G_{3} G_{1} & & G_{4} G_{0} \end{aligned} ; Table 3: H(r, k) = G_{k}(x)G_{r−k}(x).

however interested in particular cases of Proposition 1 which we state as Corollaries 2, 3, and 4.

In this paper we are interested in the relationship between the points of the Hosoya polynomial triangle and the products of generalized Fibonacci polynomials. To establish this relation we need that δ(x) = d(x) and γ(x) = g(x) where d(x) and g(x) are polynomials as defined in (1) and δ(x) and γ(x) are polynomials as defined in the Hosoya polynomial sequence. So, for the rest of the paper we assume that δ(x) = d(x) and γ(x) = g(x).

Proposition 1. H(r, k) = G_{k}(x)G_{r−k}(x).

Proof. We prove this proposition using the method of mathematical induction. Let E(k) be the statement that H(r, k) = G_{k}(x)G_{r−k}(x) for k ∈ ℤ_{≥0} and some fixed r ≥ k.

In order to prove the basis step we replace the entries of the generalized Hosoya triangle with generalized Fibonacci polynomials in the proof of [5, Proposition 1] to obtain H(r, 0) = p_{0}(x)G_{r}(x) and H(r, 1) = p_{1}(x)G_{r−1}(x) for some fixed value of r. Note that here p_{0}(x) is the polynomial G_{0}(x) and p_{1}(x) is the polynomial G_{1}(x) defined in the generalized Fibonacci polynomials and therefore the basis step is proved.

Now for the inductive step, we assume that the statements E(k − 1) and E(k) are true for k ≥ 2 and prove that E(k + 1) is true. Let r be a non-negative integer such that r ≥ k, since E(k − 1) and E(k) are true, we can write,

H(r − 2, k − 1) = G_{k−1}(x)G_{r−k−1}(x) and H(r − 1, k) = G_{k}(x)G_{r−k−1}(x).

This and the recurrence relation H(r, k + 1) = δ(x)H(r − 1, k) + γ(x)H(r − 2, k − 1) imply that

H(r, k + 1) = δ(x)G_{k}(x)G_{r−k−1}(x) + γ(x)G_{k−1}(x)G_{r−k−1}(x)
= G_{r−k−1}(x)(δ(x)G_{k}(x) + γ(x)G_{k−1}(x))
= G_{r−k−1}(x)G_{k+1}(x).

Thus, E(k + 1) is true. This proves the proposition.

We prove Corollary 2, the proofs of Corollaries 3 and 4 are similar and we omit them. The notation used in Corollaries 2, 3, and 4 are defined in Table 1. We recall that δ(x) and γ(x) represent the polynomials used to define H(r, k), and p_{0}(x) and p_{1}(x) represent the polynomials used to define G_{n}(x).

Corollary 2. If p_{0}(x) = 1 and p_{1}(x) = δ(x), then for r, k ≥ 0,

H(r, k) = \begin{cases}F_{k}(x)F_{r−k}(x), & if γ(x) = 1 and p_{1}(x) = x; \\ U_{k}(x)U_{r−k}(x), & if γ(x) = −1 and p_{1}(x) = 2x; \\ B_{k}(x)B_{r−k}(x), & if γ(x) = −1 and p_{1}(x) = x + 2; \\ P_{k}(x)P_{r−k}(x), & if γ(x) = 1 and p_{1}(x) = 2x; \\ J_{k}(x)J_{r−k}(x), & if γ(x) = 2x and p_{1}(x) = 1. \end{cases}

Proof. We prove the corollary only for the first case; the proof of other cases are similar and we omit their proofs.

Suppose that p_{0}(x) = 1, p_{1}(x) = δ(x) = x, and γ(x) = 1. We show that H(r, k) = F_{k}(x)F_{r−k}(x). If G_{n}(x) = F_{n}(x), then this along with the initial conditions given above in the proof of Proposition 1 imply that H(r, k) = F_{k}(x)F_{r−k}(x).

Corollary 3. If p_{0}(x) = 2 and p_{1}(x) = δ(x), then for r, k ≥ 0,

H(r, k) = \begin{cases}Q_{k}(x)Q_{r−k}(x), & if γ(x) = 1 and p_{1}(x) = 2x; \\ C_{k}(x)C_{r−k}(x), & if γ(x) = −1 and p_{1}(x) = x + 2; \\ D_{k}(x)D_{r−k}(x), & if γ(x) = 1 and p_{1}(x) = x; \\ j_{k}(x)j_{r−k}(x), & if γ(x) = 2x and p_{1}(x) = 1. \end{cases}

Corollary 4. If r, k ≥ 0, then

H(r, k) = \begin{cases}Φ_{k}(x)Φ_{r−k}(x), & if p_{0}(x) = γ(x) + 3 = 1 and 3δ(x) = p_{1}(x) = 3x; \\ T_{k}(x)T_{r−k}(x), & if p_{0}(x) = −γ(x) = 1 and δ(x) = 2p_{1}(x) = 2x; \\ ϑ_{k}(x)ϑ_{r−k}(x), & if p_{0}(x) = −γ(x) = 2 and 3δ(x) = p_{1}(x) = 3x. \end{cases}

As a consequence of the corollaries above, we obtain a Hosoya polynomial triangle for each of the specific polynomials mentioned in Table 1. For example, using the first result of Corollary 2 and Proposition 1 we obtain the Hosoya polynomial triangle where the entry H(r, k) is equal to F_{k}(x)F_{r−k}(x) (see Table 4). Similarly, we can obtain the Hosoya polynomial triangles with entries H(r, k) as described in Corollaries 2, 3, and 4.

x  x
x^{2} + 1  x^{2}  x^{2} + 1
x^{3} + 2x  x^{3} + x  x^{3} + x  x^{3} + 2x
x^{4} + 3x^{2} + 1  x(x^{3} + 2x)  (x^{2} + 1)^{2}  x(x^{3} + 2x)  x^{4} + 3x^{2} + 1

Table 4: The Hosoya polynomial triangle where H(r, k) = F_{k}(x)F_{r−k}(x).

3 Alternating sum of points in a row of the Hosoya polynomial triangle

We begin this section by presenting some numerical examples of alternating sums. We follow this up with a discussion on Binet formulas which play an important role in the proof of the main results of this paper. We finally state and prove the main results at the end of this section.

3.1 Examples

If we set x = 1 in Table 4, then we obtain the regular Hosoya triangle, see Table 5. Note that the alternating sum of all points in an odd row of this triangle is zero, due to the symmetry of the triangle. However, the alternating sum of all points in an even row does not satisfy this property. For instance, if we take the alternating sum of all points in the second, fourth, and sixth row of Table 5, the results are F_{3}, F_{5}, and F_{7}, respectively, (see the following example).

2 − 1 + 2 = 3 = F_{3}; 5 − 3 + 4 − 3 + 5 = 8 = F_{5}; 13 − 8 + 10 − 9 + 10 − 8 + 13 = 21 = F_{7}.

From this example and Table 5 we can see that

∑_{i=0}^{2t}(−1)^{i}H(2t, i) = ∑_{i=0}^{2t}(−1)^{i}F_{i} · F_{2t−i} = F_{2t+1}.

We now give two examples that generalize this fact to polynomials. If we take H(r, k) = F_{k}(x)F_{r−k}(x) then the alternating sum of the terms in an even row of the Hosoya polynomial triangle is the quotient of two Fibonacci polynomials. The following is the alternating sum of all points on the fourth row of Table 4.

∑_{i=0}^{4}(−1)^{i}H(4, i) = ∑_{i=0}^{4}(−1)^{i}F_{i}(x) · F_{4−i}(x)

= (x^{4} + 3x^{2} + 1) − (x^{4} + 2x^{2}) + (x^{2} + 1)^{2} − (x^{4} + 2x^{2}) + (x^{4} + 3x^{2} + 1) = x^{4} + 4x^{2} + 3

= \frac{F_{5}(x)}{F_{1}(x)}.

1 1
2 1 2
3 2 2 3
5 3 4 3 5
8 5 6 6 5 8
13 8 10 9 10 8 13

Table 5: The Hosoya triangle.

If we take H(r, k) = B_{k}(x)B_{r−k}(x), then we obtain

∑_{i=0}^{4}(−1)^{i}H(4, i) = ∑_{i=0}^{4}(−1)^{i}B_{i}(x) · B_{4−i}(x)

= x^{4} + 8x^{3} + 20x^{2} + 16x + 5

= \frac{B_{5}(x)}{B_{1}(x)}.

Those examples will be stated in Corollary 8. Note that this property does not hold for every choice of H(r, k). For example, if we take H(r, k) = T_{k}(x)T_{r−k}(x), then it is easy to see that ∑_{i=0}^{2}(−1)^{i}T_{i}(x) · T_{2t−i}(x) ≠ T_{3}(x)/T_{1}(x). We analyze this case in Corollary 10.

3.2 Binet formulas

A generalized Fibonacci polynomial which satisfies the Binet formula (2) is said to be of first type and it is of second type if it satisfies the Binet formula (3). Horadam [8] and André-Jeannin [1] have studied these polynomials in detail. The following are the Binet formulas mentioned above,

L_{n}(x) = \frac{a^{n}(x) + b^{n}(x)}{α},  (2)

R_{n}(x) = \frac{a^{n+1}(x) − b^{n+1}(x)}{a(x) − b(x)},  (3)

where a(x) + b(x) = d(x) and a(x)b(x) = −g(x). If d^{2}(x) + 4g(x) ≥ 0, then we have a(x) − b(x) = \sqrt{d^{2}(x) + 4g(x)} where d(x) and g(x) are the polynomials defined on the generalized Fibonacci polynomials.

The sequence of polynomials that have Binet representations R_{n}(x) or L_{n}(x) depend only on d(x) and g(x) defined on the generalized Fibonacci polynomials. We say that a generalized Fibonacci sequence of first (second) type is equivalent to a sequence of the second (first) type, if their recursive sequences are determined by the same polynomials d(x) and g(x). Notice that two equivalent polynomials have the same a(x) and b(x) in their Binet representations.

For example, the Lucas polynomial is of first type, whereas the Fibonacci polynomial is of second type. Lucas and Fibonacci polynomials are equivalent because d(x) = x and g(x) = 1 (see Table 1). Note that in their Binet representations they both have a(x) = (x+\sqrt{x^{2} + 4})/2 and b(x) = (x − \sqrt{x^{2} + 4})/2. We use the results in [1] and [8] to classify all polynomials in Table 1 as pairs of equivalent polynomials (see Table 6). The leftmost polynomials in Table 6 are of the first type their equivalent polynomials are in the third column on the same line. In the last two columns of Table 6 we can see the a(x) and b(x) that the pairs of equivalent polynomials share. It is easy to obtain the characteristic equations of the sequences given in Table 1, and the roots of the equations are a(x) and b(x).

Polynomial L_{n}(x) Polynomial of R_{n}(x) a(x) b(x)
First type  Second type
Lucas  D_{n}(x) Fibonacci  F_{n}(x) (x + \sqrt{x^{2} + 4})/2  (x − \sqrt{x^{2} + 4})/2
Pell-Lucas  Q_{n}(x) Pell  P_{n}(x) x + \sqrt{x^{2} + 1}  x − \sqrt{x^{2} + 1}
Fermat-Lucas  ϑ_{n}(x) Fermat  Φ_{n}(x) (3x + \sqrt{9x^{2} − 8})/2  (3x − \sqrt{9x^{2} − 8})/2
Chebyshev first kind T_{n}(x) Chebyshev second kind U_{n}(x) x + \sqrt{x^{2} − 1}  x − \sqrt{x^{2} − 1}
Jacobsthal-Lucas  j_{n}(x) Jacobsthal  J_{n}(x) (1 + \sqrt{1 + 8x})/2  (1 − \sqrt{1 + 8x})/2
Morgan-Voyce  C_{n}(x) Morgan-Voyce  B_{n}(x) (x + 2 + \sqrt{x^{2} + 4x})/2 (x + 2 − \sqrt{x^{2} + 4x})/2
Table 6: R_{n}(x) equivalent to L_{n}(x).

3.3 Main results

Lemma 5. The equivalent sequence of a generalized Fibonacci polynomial sequence always exists.

Proof. Without loss of generality we suppose that G_{n}(x) is a generalized Fibonacci polynomial sequence of the first type. From the Binet formula (2) we know that there are a(x) and b(x) such that a(x) + b(x) = d(x), a(x)b(x) = −g(x), and when d^{2}(x) + 4g(x) ≥ 0, we have a(x) − b(x) = \sqrt{d^{2}(x) + 4g(x)}. It is easy to see that a(x) and b(x) give rise to a polynomial of the second type.

Lemma 6. If G_{k}(x) is a generalized Fibonacci polynomial that satisfies the Binet formula given in (3), then

∑_{k=0}^{∞} G_{k}(x)t^{k} = \frac{1}{(1 − a(x)t)(1 − b(x)t)}.

Proof. Let f(t, x) be ∑_{k=0}^{∞} G_{k}(x)t^{k}. Since the sequence G_{n}(x) satisfies the Binet formula given in (3), G_{n}(x) = [a^{n+1}(x) − b^{n+1}(x)] / [a(x) − b(x)]. Therefore,

f(t, x) = ∑_{k=0}^{∞} \frac{a^{k+1}(x) − b^{k+1}(x)}{a(x) − b(x)}t^{k}.  (4)

It is known that ∑_{k=0}^{∞} αt^{k} = α/(1 − t). This and the functions a(x) and b(x), imply that

∑_{k=0}^{∞} a(x) (a(x)t)^{k} = \frac{a(x)}{1 − a(x)t}, and ∑_{k=0}^{∞} b(x) (b(x)t)^{k} = \frac{b(x)}{1 − b(x)t}.

Therefore, these two generating functions, and (4) imply that

f(t, x) = \frac{1}{a(x) − b(x)} ∑_{k=0}^{∞} (a^{k+1}(x) − b^{k+1}(x)) t^{k} = \frac{1}{a(x) − b(x)} (\frac{a(x)}{1 − a(x)t} − \frac{b(x)}{1 − b(x)t}) .

So, simplifying we obtain that f(t, x) = 1/ [(1 − a(x)t)(1 − b(x)t)] .

Theorem 7. If G_{n}(x) is a generalized Fibonacci polynomial that satisfies the Binet formula given in (3), then

∑_{k=0}^{r}(−1)^{k}H(r, k) = \begin{cases}G_{r+1}(x)/G_{1}(x), & if r is even; \\ 0, & if r is odd. \end{cases}

Proof. If r is odd, by symmetry of the Hosoya polynomial triangle, it is easy to see that ∑_{k=0}^{r}(−1)^{k}G_{k}(x)G_{r−k}(x) = 0. To prove the case where r is even, we use generating functions. Let f(t, x) be ∑_{k=0}^{∞} G_{k}(x)t^{k}. Since G_{k}(x) satisfies the Binet formula given in (3), by Lemma 6 we have that f(t, x) is equal to 1/ [(1 − a(x)t)(1 − b(x)t)]. Therefore,

f(t, x) − f(−t, x) = \frac{1}{(1 − a(x)t)(1 − b(x)t)} − \frac{1}{(1 + a(x)t)(1 + b(x)t)}
= \frac{2t(a(x) + b(x))}{(1 − a(x)t)(1 − b(x)t)(1 + a(x)t)(1 + b(x)t)}.

Simplifying we have that

f(t, x) − f(−t, x) = 2(a(x) + b(x))tf(t, x)f(−t, x)
= \frac{2(a^{2}(x) − b^{2}(x))}{a(x) − b(x)}tf(t, x)f(−t, x)
= 2G_{1}(x)tf(t, x)f(−t, x)
= 2G_{1}(x)t (∑_{k=0}^{∞} G_{k}(x)t^{k}) (∑_{k=0}^{∞} G_{k}(x)(−t)^{k}) .

Thus,

f(t, x) − f(−t, x) = 2G_{1}(x) ∑_{r=0}^{∞} (∑_{k=0}^{r}(−1)^{r−k}G_{k}(x)G_{r−k}(x)) t^{r+1}.  (5)

We note that f(t, x) − f(−t, x) is also equal to

∑_{j=0}^{∞} G_{j}(x)t^{j} − ∑_{j=0}^{∞} G_{j}(x)(−t)^{j} = ∑_{j=0}^{∞}(1 − (−1)^{j})G_{j}(x)t^{j} = 2 ∑_{j=0}^{∞} G_{2j+1}(x)t^{2j+1}.

From the right side of this last equality and from the right side of (5) we have that

∑_{r=0}^{∞} 2G_{1}(x) (∑_{k=0}^{r}(−1)^{r−k}G_{k}(x)G_{r−k}(x)) t^{r+1} = ∑_{j=0}^{∞} 2G_{2j+1}(x)t^{2j+1}.

It is known that two generating functions are equal if their corresponding coefficients of t^{i} are equal for all i. We are only interested in the cases when r is even. So, we analyze the case in which r + 1 = 2j + 1 in the last equality above. Thus, if r + 1 = 2j + 1, then

2G_{1}(x) ∑_{k=0}^{r}(−1)^{r−k}G_{k}(x)G_{r−k}(x) = 2G_{2j+1}(x),

simplifying,

∑_{k=0}^{r}(−1)^{r−k}G_{k}(x)G_{r−k}(x) = \frac{G_{r+1}(x)}{G_{1}(x)}.

Since H(r, k) = G_{k}(x)G_{r−k}(x), this completes the proof of the theorem.

The notation used in Corollaries 8 and 10 are defined in Tables 1 and 6.

Corollary 8. If t is a positive integer, then ∑_{i=0}^{2t+1}(−1)^{i}H(2t + 1, i) = 0, and

∑_{i=0}^{2t}(−1)^{i}H(2t, i) = \begin{cases}F_{2t+1}(x)/F_{1}(x), & if H(2t, i) = F_{i}(x)F_{2t−i}(x); \\ B_{2t+1}(x)/B_{1}(x), & if H(2t, i) = B_{i}(x)B_{2t−i}(x); \\ P_{2t+1}(x)/P_{1}(x), & if H(2t, i) = P_{i}(x)P_{2t−i}(x); \\ J_{2t+1}(x)/J_{1}(x), & if H(2t, i) = J_{i}(x)J_{2t−i}(x); \\ Φ_{2t+1}(x)/Φ_{1}(x), & if H(2t, i) = Φ_{i}(x)Φ_{2t−i}(x); \\ U_{2t+1}(x)/U_{1}(x), & if H(2t, i) = U_{i}(x)U_{2t−i}(x). \end{cases}

Proof. We prove the corollary only for the case in which H(2t, i) = F_{i}(x)F_{2t−i}(x), the proof of the other five cases are similar. Therefore, omit their proofs.

From Table 6 we know that F_{n}(x) is of second type, therefore it satisfies (3) where a(x) = (x+\sqrt{x^{2} + 4})/2 and b(x) = (x−\sqrt{x^{2} + 4})/2. This and Theorem 7 with G_{k}(x) = F_{k}(x) imply that

∑_{i=0}^{2t}(−1)^{i}H(2t, i) = \frac{F_{2t+1}(x)}{F_{1}(x)}.

This proves the corollary.

Theorem 9. If G_{n}(x) is a generalized Fibonacci polynomial that satisfies the Binet formula (2), then for r ≥ 2

∑_{k=0}^{r}(−1)^{k}H(r, k) = \begin{cases}\frac{(G_{0}(x))^{2}R_{r+1}(x) − (G_{1}(x))^{2}R_{r−1}(x)}{R_{1}(x)}, & if r is even; \\ 0; & if r is odd. \end{cases}

where R_{n}(x) is equivalent to G_{n}(x).

Proof. If r is odd, by symmetry of the Hosoya polynomial triangle, it is easy to see that ∑_{k=0}^{r}(−1)^{k}G_{k}(x)G_{r−k}(x) = 0. To prove the case in which r is even, we use generating functions. We suppose that G_{n}(x) is a sequence of generalized Fibonacci polynomials which satisfy Binet formula (2) and let R_{n}(x) be its equivalent sequence of polynomials which satisfy Binet formula (3). Let g(t, x) be ∑_{k=0}^{∞} G_{k}(x)t^{k} and let f(t, x) be ∑_{k=0}^{∞} R_{k}(x)t^{k}. Since R_{n}(x) satisfies the Binet formula given in (3), by Lemma 6 we have that f(t, x) is equal to 1/ [(1 − a(x)t)(1 − b(x)t)] .

Since G_{n}(x) satisfies (2), taking α = 1 we obtain

g(t, x) = ∑_{k=0}^{∞}(a(x)^{k} + b(x)^{k})t^{k}

= ∑_{k=0}^{∞}(a(x)t)^{k} + ∑_{k=0}^{∞}(b(x)t)^{k}
= \frac{1}{1 − a(x)t} + \frac{1}{1 − b(x)t}
= \frac{2 − (a(x) + b(x))t}{(1 − a(x)t)(1 − b(x)t)}.

Since f(t, x) = 1/ [(1 − a(x)t)(1 − b(x)t)], we have that g(t, x) = (2 − (a(x) + b(x))t) f(t, x). This implies that

g(t, x)g(−t, x) = (4 − (a(x) + b(x))^{2}t^{2}) f(t, x)f(−t, x).

This, the definition of g(t, x), and the definition of f(t, x), imply that

∑_{r=0}^{∞} G_{r}(x)t^{r} ∑_{r=0}^{∞} G_{r}(x)(−t)^{r} = (4 − (a(x) + b(x))^{2}t^{2}) ∑_{r=0}^{∞} R_{r}(x)t^{r} ∑_{r=0}^{∞} R_{r}(x)(−t)^{r}.

Thus,

∑_{r=0}^{∞} (∑_{k=0}^{r}(−1)^{k}G_{k}(x)G_{r−k}(x)) t^{r} = (4 − (a(x) + b(x))^{2}t^{2}) ∑_{l=0}^{∞} (∑_{k=0}^{l}(−1)^{k}R_{k}(x)R_{l−k}(x)) t^{l}

for l even. Since R_{k}(x) satisfies that Binet formula (3), Theorem 7 implies

∑_{r=0}^{∞} (∑_{k=0}^{r}(−1)^{k}G_{k}(x)G_{r−k}(x)) t^{r} = (4 − (a(x) + b(x))^{2}t^{2}) ∑_{j=0}^{∞} \frac{R_{2j+1}(x)}{R_{1}(x)}t^{2j}

= ∑_{j=0}^{∞} \frac{4R_{2j+1}(x)}{R_{1}(x)}t^{2j} − ∑_{j=0}^{∞}(a(x) + b(x))^{2} \frac{R_{2j+1}(x)}{R_{1}(x)}t^{2j+2}

= 4 + ∑_{j=1}^{∞} (\frac{4R_{2j+1}(x) − (a(x) + b(x))^{2}R_{2j−1}(x)}{R_{1}(x)}) t^{2j}.

Since G_{1}(x) = a(x) + b(x) we have that

∑_{r=0}^{∞} (∑_{k=0}^{r}(−1)^{k}G_{k}(x)G_{r−k}(x)) t^{r} = 4t^{0} + ∑_{j=1}^{∞} (\frac{4R_{2j+1}(x) − (G_{1}(x))^{2}R_{2j−1}(x)}{R_{1}(x)}) t^{2j}.

It is known that two generating functions are equal if the corresponding coefficients of t^{i} are equal for all i. We are only interested in even values of r. Therefore, we analyze the case when r = 2j in the last equality above. If r = 2j with j > 0 and G_{0}(x) = 2, then

∑_{k=0}^{r}(−1)^{k}G_{k}(x)G_{r−k}(x) = \frac{(G_{0}(x))^{2}R_{r+1}(x) − (G_{1}(x))^{2}R_{r−1}(x)}{R_{1}(x)}.

If α ≠ 1, we let Gk^{′}(x) be (a^{k}(x) + b^{k}(x))/α, we recall from the previous analysis that G_{k}(x) = a^{k}(x) + b^{k}(x). Note that the equivalent polynomial R_{k}(x) of G_{k}(x) is the same for Gk^{′}(x), because they contain the same a^{k}(x) and b^{k}(x). Therefore,

∑_{k=0}^{r}(−1)^{k}Gk^{′}(x)Gr−k^{′}(x) = \frac{1}{α^{2}} ∑_{k=0}^{r}(−1)^{k}G_{k}(x)G_{r−k}(x)

= \frac{1}{α^{2}} \frac{(G_{0}(x))^{2}R_{r+1}(x) − (G_{1}(x))^{2}R_{r−1}(x)}{R_{1}(x)}
= \frac{(G_{0}(x)/α)^{2}R_{r+1}(x) − (G_{1}(x)/α)^{2}R_{r−1}(x)}{R_{1}(x)}
= \frac{(G0^{′}(x))^{2}R_{r+1}(x) − (G1^{′}(x))^{2}R_{r−1}(x)}{R_{1}(x)}.

This proves the theorem.

Corollary 10. If t is a positive integer and r = 2t, then ∑_{i=0}^{r+1}(−1)^{i}H(r + 1, i) = 0, and

∑_{i=0}^{r}(−1)^{i}H(r, i) = \begin{cases}(U_{r+1}(x) − x^{2}U_{r−1}(x))/U_{1}(x), & if H(r, i) = T_{i}(x)T_{r−i}(x); \\ (4F_{r+1}(x) − x^{2}F_{r−1}(x))/F_{1}(x), & if H(r, i) = D_{i}(x)D_{r−i}(x); \\ (4Φ_{r+1}(x) − 9x^{2}Φ_{r−1}(x))/Φ_{1}(x), & if H(r, i) = ϑ_{i}(x)ϑ_{r−i}(x); \\ (4P_{r+1}(x) − 4x^{2}P_{r−1}(x))/P_{1}(x), & if H(r, i) = Q_{i}(x)Q_{r−i}(x); \\ (4J_{r+1}(x) − J_{r−1}(x))/J_{1}(x), & if H(r, i) = j_{i}(x)j_{r−i}(x); \\ (4B_{r+1}(x) − (x + 2)^{2}B_{r−1}(x))/B_{1}(x), & if H(r, i) = C_{i}(x)C_{r−i}(x). \end{cases}

Proof. We prove the corollary only for the case in which H(r, i) = T_{i}(x)T_{r−i}(x); the proof of the other five cases are similar. Therefore, we omit their proofs.

From Table 6 we know that T_{n}(x) is of first type and satisfies the Binet formula (2). So, G_{n}(x) = T_{n}(x) and R_{n}(x) = U_{n}(x). Thus, T_{n}(x) = ((x + \sqrt{x^{2} − 1})^{n} + (x − \sqrt{x^{2} − 1})^{n})/2. This and Theorem 9 where H(r, k) = T_{k}(x)T_{r−k}(x) imply that

∑_{k=0}^{r}(−1)^{k}H(r, k) = \begin{cases}\frac{U_{r+1}(x) − x^{2}U_{r−1}(x)}{U_{1}(x)}, & if r nonzero even; \\ 0, & if r is odd. \end{cases}

This proves the corollary.

4 Particular cases and examples

In this section we study some numerical cases of the Hosoya polynomial triangles. We show that when we evaluate the entries of a Hosoya polynomial triangle at some integer numbers, the alternating sums found in Section 3 give rise to several well-known sequences published in The On-Line Encyclopedia of Integer Sequences [16] by different authors.

We define an n-initial Hosoya triangle as the finite triangular arrangement formed by the first n-rows of the Hosoya triangle. Note that the initial triangle is the equilateral subtriangle of any Hosoya triangle that contains the vertex H(0, 0). In Proposition 11 we prove that the sum of all alternating sums of any initial triangle of the classical Hosoya triangle (see Table 5) is a closed formula depending on a Fibonacci number. We recall that in this paper the Fibonacci numbers are

F_{0} = 1, F_{1} = 1, F_{2} = 2, F_{3} = 3, F_{4} = 5, F_{5} = 8, ….

Proposition 11. Let n be a positive integer and t = ⌊n/2⌋ + 1. If H(r, k)(1) = F_{k}F_{r−k} then

∑_{0≤k≤r≤n}(−1)^{k}H(r, k)(1) = ∑_{i=0}^{t−1}(t − i)F_{2i} = F_{2t} − 1.

Proof. We prove ∑_{0≤k≤r≤n}(−1)^{k}H(r, k)(1) = F_{2n+1} − 1, the other equality is known. From Corollary 8 we know that ∑_{i=0}^{2t}(−1)^{k}H(r, k)(1) = F_{2t+1} and ∑_{i=0}^{2t+1}(−1)^{k}H(r, k)(1) = 0. This implies that ∑_{0≤k≤r≤n}(−1)^{k}H(r, k) = ∑_{t=0}^{n} F_{2(n−i)} = F_{2n} − 1.

We now introduce some notation that are used in Table 7. We define

C(·)(x) = ∑_{r=0}^{n}(−1)^{k}H(r, k)

where (·) depends on the polynomials used in the sequences. For example, CF_{n}(x) is the notation that we use to indicate the first result in Corollary 8. If we evaluate CF_{n}(x) at x = 2 for n ∈ ℕ we obtain the sequence 1, 6, 35, 204, 1189, 6930 which is in http://oeis.org/A001109 (see Sloane [16]). We use CM_{n}(x) to indicate the second result in Corollary 8. Similarly we use CP_{n}(x) and CJ_{n}(x), to indicate the third and fourth results in Corollary 8, respectively. In Table 7 we present some known sequences. Thus, the Corollaries 8 and 10 provide another way to generate sequences. Note that for the case Fermat and Chebyshev in Corollary 8 we only found the sequences \underline{A002450} and \underline{A007954}, respectively.

CF_{n}(x) Sloane CM_{n}(x) Sloane  CP_{n}(x) Sloane CJ_{n}(x) Sloane
CF_{n}(1) \underline{A001906} CM_{n}(1) \underline{A04187} CP_{n}(1) \underline{A001109} CJ_{n}(1) \underline{A002450}
CF_{n}(2) \underline{A001109} CM_{n}(2) \underline{A007655} CP_{n}(2) \underline{A049660} CJ_{n}(2) \underline{A102902}
CF_{n}(3) \underline{A004190} CM_{n}(3) \underline{A097778} CP_{n}(3) \underline{A078987} CJ_{n}(3) \underline{A016153}
CF_{n}(4) \underline{A049660} CM_{n}(4) \underline{A029547} CP_{n}(4) \underline{A097316}
CF_{n}(5) \underline{A097781} CM_{n}(5) \underline{A049668} CP_{n}(5) \underline{A097725}
CF_{n}(6) \underline{A078987}  CP_{n}(6) \underline{A097728}
CF_{n}(7) \underline{A097836}  CP_{n}(7) \underline{A097731}
CF_{n}(8) \underline{A097316} CM_{n}(8) \underline{A173205} CP_{n}(8) \underline{A097734}
CF_{n}(9) \underline{A097839}  CP_{n}(9) \underline{A097737}
CF_{n}(10) \underline{A097725}  CP_{n}(10) \underline{A097740}

Table 7: Some sequences from Corollary 8 that are in [16].

5 Acknowledgement

The first and the last authors were partially supported by The Citadel Foundation.

References

[1] R. André-Jeannin, Differential properties of a general class of polynomials, Fibonacci Quart. 33 (1995), 453–458.

[2] R. André-Jeannin, A note on a general class of polynomials, II, Fibonacci Quart. 33 (1995), 341–351.

[3] R. André-Jeannin, A note on a general class of polynomials, Fibonacci Quart. 32 (1994), 445–454.

[4] R. André-Jeannin, A generalization of Morgan-Voyce polynomials, Fibonacci Quart. 32 (1994), 228–231.

[5] R. Flórez, R. Higuita and L. Junes, GCD property of the generalized star of David, J. Integer Seq. 17 (2014), Article 14.3.6, 17 pp.

[6] R. Flórez and L. Junes, GCD properties in Hosoya’s triangle, Fibonacci Quart. 50 (2012), 163–174.

[7] V. E. Jr. Hoggatt and M. Bicknell-Johnson, Divisibility properties of polynomials in Pascal’s triangle, Fibonacci Quart. 16 (1978), 501–513.

[8] A. F. Horadam, A synthesis of certain polynomial sequences, Applications of Fibonacci numbers, Vol. 6 (Pullman, WA, 1994), 215–229, Kluwer Acad. Publ., Dordrecht, 1996.

[9] A. F. Horadam and J. M. Mahon, Pell and Pell-Lucas polynomials, Fibonacci Quart. 23 (1985), 7–20.

[10] A. F. Horadam, Chebyshev and Fermat polynomials for diagonal functions, Fibonacci Quart. 17 (1979), 328–333.

[11] H. Hosoya, Fibonacci triangle, Fibonacci Quart. 14 (1976), 173–178.

[12] T. Koshy, Fibonacci and Lucas numbers with applications, Wiley-Interscience, New York, 2001.

[13] J. Lahr, Fibonacci and Lucas numbers and the Morgan-Voyce polynomials in ladder networks and in electric line theory, Fibonacci numbers and their applications (Patras, 1984), 141–161.

[14] A. M. Morgan-Voyce, Ladder network analysis using Fibonacci numbers, IRE Trans. Circuit Th. CT-6 (1959), 321–322.

[15] M. N. S. Swamy, Properties of the polynomials defined by Morgan-Voyce, Fibonacci Quart. 4 (1966a), 73–81.

[16] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org/.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 11B83. Keywords: Hosoya triangle, generalized Fibonacci polynomial, alternating sum, Fibonacci polynomial, Chebyshev polynomial, Morgan-Voyce polynomial, Lucas polynomial, Pell polynomial, Fermat polynomial.

(Concerned with sequences \underline{A001109}, \underline{A001906}, \underline{A002450}, \underline{A004190}, \underline{A007655}, \underline{A007954}, \underline{A016153}, \underline{A029547}, \underline{A049660}, \underline{A049668}, \underline{A078987}, \underline{A097316}, \underline{A097725}, \underline{A097728}, \underline{A097731}, \underline{A097734}, \underline{A097737}, \underline{A097740}, \underline{A097778}, \underline{A097781}, \underline{A097836}, \underline{A097839}, \underline{A102902}, and \underline{A173205}.)

Received April 4 2014; revised version received August 20 2014. Published in Journal of Integer Sequences, September 3 2014.

Return to Journal of Integer Sequences home page.