A Graph-Theoretic Model for a Generalized Fibonacci Gem

Thomas Koshy Department of Mathematics Framingham State University Framingham, MA 01701 USA

                 tkoshy@emeriti.framingham.edu

Abstract We extend a charming Fibonacci pleasantry to Fibonacci, Lucas, Jacobsthal, and Jacobsthal-Lucas polynomials; and then confirm the resulting polynomial delights using graph-theoretic tools.

1 Introduction

Generalized Fibonacci polynomials z_{n}(x) are defined by the recurrence z_{n}(x) = a(x)z_{n−1}(x)+ b(x)z_{n−2}(x), where x is an arbitrary complex variable; a(x), b(x), z_{0}(x), and z_{1}(x) are arbitrary complex polynomials; and n ≥ 2.

Let a(x) = x and b(x) = 1. When z_{0}(x) = 0 and z_{1}(x) = 1, z_{n}(x) = f_{n}(x), the nth Fibonacci polynomial; and when z_{0}(x) = 2 and z_{1}(x) = x, z_{n}(x) = l_{n}(x), the nth Lucas polynomial. Clearly, f_{n}(1) = F_{n}, the nth Fibonacci number; and l_{n}(1) = L_{n}, the nth Lucas number [2, 3, 12, 13].

Pell polynomials p_{n}(x) and Pell-Lucas polynomials q_{n}(x) are defined by p_{n}(x) = f_{n}(2x) and q_{n}(x) = l_{n}(2x), respectively. The Pell numbers P_{n} and Pell-Lucas numbers Q_{n} are given by P_{n} = p_{n}(1) = f_{n}(2) and 2Q_{n} = q_{n}(1) = l_{n}(2), respectively [7, 10].

Suppose a(x) = 1 and b(x) = x. When z_{0}(x) = 0 and z_{1}(x) = 1, z_{n}(x) = J_{n}(x), the nth Jacobsthal polynomial; and when z_{0}(x) = 2 and z_{1}(x) = 1, z_{n}(x) = j_{n}(x), the nth Jacobsthal-Lucas polynomial [5, 6]. Correspondingly, J_{n} = J_{n}(2) and j_{n} = j_{n}(2) are the nth Jacobsthal and Jacobsthal-Lucas numbers, respectively. Clearly, J_{n}(1) = F_{n}; and j_{n}(1) = L_{n}.

The polynomials f_{n}(x), l_{n}(x), J_{n}(x), and j_{n}(x) can also be defined explicitly using Binetlike formulas:

\begin{matrix}f_{n}(x) = \frac{α^{n} − β^{n}}{α − β}; & l_{n}(x) = α^{n} + β^{n}; \\ J_{n}(x) = \frac{u^{n} − v^{n}}{u − v}; & j_{n}(x) = u^{n} + v^{n}, \end{matrix}

where α = α(x) and β = β(x) are the solutions of the equation t^{2} − xt − 1, and u = u(x); and v = v(x) are those of t^{2} − t − x = 0. Notice that α − β = \sqrt{x^{2} + 4} and u − v = \sqrt{4x + 1}.

In the interest of brevity, clarity, and convenience, we omit the argument in the functional notation, when there is no ambiguity; so z_{n} means z_{n}(x). In addition, we let g_{n} = f_{n} or l_{n}; b_{n} = p_{n} or q_{n}; and c_{n} = J_{n}(x) or j_{n}(x); and correspondingly, G_{n} = F_{n} or L_{n}; B_{n} = P_{n} or Q_{n}; and C_{n} = J_{n} or j_{n}.

2 Q-matrix and digraph

Gibonacci polynomials f_{n} and l_{n} can be studied using the Q-matrix

Q = [\begin{matrix}x & 1 \\ 1 & 0 \end{matrix}] ,

where Q = Q(x) = (q_{ij})_{2×2} [11, 14]. It then follows by induction that

Q^{n} = [\begin{matrix}f_{n+1} & f_{n} \\ f_{n} & f_{n−1} \end{matrix}] ,

where n ≥ 1.

The Q-matrix has a graph-theoretic appeal. It can be interpreted as the weighted adjacency matrix of a weighted digraph D_{1} with vertices v_{1} and v_{2} [11, 14]; see Figure 1. Notice that a weight is assigned to each edge.

A walk from vertex v_{i} to vertex v_{j} is a sequence v_{i}-e_{i}-v_{i+1}-⋯ -v_{j−1}-e_{j−1}-v_{j} of vertices v_{k} and edges e_{k}, where edge e_{k} is incident with vertices v_{k} and v_{k+1}. The walk is closed if v_{i} = v_{j}; otherwise, it is open. The length of a walk is the number of edges in the walk. The weight of a walk is the product of the weights of the edges along the walk.

We can employ the weighted adjacency matrix to compute the weight of a walk of length n from any vertex v_{i} to any vertex v_{j}, as the following theorem shows [9, 11].

Figure 1: Weighted digraph D_{1}

Theorem 1. Let A be the weighted adjacency matrix of a weighted and connected digraph with vertices v_{1}, v_{2}, …, v_{k}. Then the ijth entry of the matrix A^{n} gives the sum of the weights of all walks of length n from v_{i} to v_{j}, where n ≥ 1.

This theorem implies the following result.

Corollary 2. The ijth entry of Q^{n} gives the sum of the weights of all walks of length n from v_{i} to v_{j} in the weighted digraph D_{1}, where 1 ≤ i, j ≤ 2.

It follows by this corollary that the sum of the weights of all closed walks of length n originating in the digraph model is f_{n+1}, and that of walks of length n originating at v_{2} is f_{n−1}. So the sum of the weights of all closed walks of length n is f_{n+1} + f_{n−1} = l_{n}.

3 A Gibonacci delight

In 1963, H. W. Gould established a charming identity for Fibonacci squares [8, 13]:

F_{n+3}^{2} = 2F_{n+2}^{2} + 2F_{n+1}^{2} − F_{n}^{2}.  (1)

It has a simple, but delightful geometric interpretation [13].

The next theorem extends identity (1) to gibonacci polynomials g_{n}.

Theorem 3.

g_{n+3}^{2} = f_{3}g_{n+2}^{2} + f_{3}g_{n+1}^{2} − g_{n}^{2}.  (2)

Proof. Using the gibonacci recurrence, we have

g_{n+3}^{2} + g_{n}^{2} = (xg_{n+2} + g_{n+1})^{2} + (g_{n+2} − xg_{n+1})^{2}
= (x^{2} + 1)g_{n+2}^{2} + (x^{2} + 1)g_{n+1}^{2}.

This yields the desired identity. (It also follows by Binet’s formulas.)

4 Graph-theoretic models

With these tools at our finger tips, we can give graph-theoretic interpretations of the gibonacci results in Theorem 3. The essence of our technique hinges on Corollary 2, and the “weighted”version of Fubini’s principle [1, 13]: Counting the number of elements in a set in two different ways yields the same result.

We begin our discourse with g_{n} = f_{n}.

4.1 Interpretation with g_{n} = f_{n}

It follows by Corollary 2 that the sum of the weights of closed walks of length n+2 originating at v_{1} is f_{n+3}. The sum S of the weights of ordered pairs (v, w) of such closed walks is the product of the sum of the weights of such walks v and w. Consequently, S = f_{n+3}^{2}.

We will now compute the sum S in a different way.

Proof. Case 1. Suppose v and w begin with a loop at v_{1}. The sum of the weights of pairs (v, w) of such closed walks of length n + 2 is (xf_{n+2})(xf_{n+2}) = x^{2}f_{n+2}^{2}.

Case 2. Suppose v begins with a loop at v_{1}, but w does not. The sum of the weights of pairs of such closed walks is (xf_{n+2})(1 · 1 · f_{n}) = xf_{n+2}f_{n}.

Case 3. On the other hand, suppose v does not begin with a loop, but w does. The sum of the weights of pairs of such closed walks is (1 · 1 · f_{n})(xf_{n+2}) = xf_{n+2}f_{n}.

Case 4. Finally, suppose neither v nor w begins with a loop. The contribution of pairs of such walks toward the sum S is (1 · f_{n+1})(1 · f_{n+1}) = f_{n+1}^{2}.

Combining the four cases, we also get

S = x^{2}f_{n+2}^{2} + f_{n+1}^{2} + 2xf_{n+2}f_{n}
= (x^{2} + 1)f_{n+2}^{2} + (x^{2} + 1)f_{n+1}^{2} − f_{n}^{2},

as in the proof of Theorem 3.

Equating the cumulative sums yields the desired result.

As a byproduct, this discourse then gives a graph-theoretic proof of the Pell identity

p_{n+3}^{2} = p_{3}p_{n+2}^{2} + p_{3}p_{n+1}^{2} − p_{n}^{2}.

Next we investigate the graph-theoretic interpretation of identity (2) with g_{n} = l_{n}.

4.2 Interpretation with g_{n} = l_{n}

Proof. Let A denote the set of closed walks of length n + 3 originating at v_{1}, and B that of length n + 3 originating at v_{2}. Let C = A ∪ B, where A ∩ B = ∅. The sum of the weights of all closed walks in C equals f_{n+4} + f_{n+2} = l_{n+3}. Consequently, the sum S of the weights of ordered pairs (v, w) ∈ C × C is given by S = l_{n+3}^{2}.

To compute this sum in a different way, first we make an interesting observation. By Theorem 3, we have

x^{2}f_{n+3}^{2} + 4f_{n+2}^{2} + 4xf_{n+3}f_{n+2} = (xf_{n+3} + 2f_{n+2})^{2}
= (f_{n+4} + f_{n+2})^{2}
= l_{n+3}^{2}  (3)
= f_{3}l_{n+2}^{2} + f_{3}l_{n+1}^{2} − l_{n}^{2}.

Consequently, it suffices to establish graph-theoretically the equivalent identity

x^{2}f_{n+3}^{2} + 4f_{n+2}^{2} + 4xf_{n+3}f_{n+2} = l_{n+3}^{2}.  (4)

We will accomplish this using four cases for an arbitrary element (v, w) ∈ C × C.

Case 1. Suppose v, w ∈ A. Suppose both v and w begin with a loop. The sum of the weights of pairs (v, w) of such closed walks is (xf_{n+3})(xf_{n+3}) = x^{2}f_{n+3}^{2}. If v begins with a loop at v_{1} and w does not, then v ∈ A and w ∈ B. The sum of the weights of all such pairs (v, w) of closed walks equals (x·f_{n+3})(1·1·f_{n+2}) = xf_{n+3}f_{n+2}. Suppose v does not begin with a loop, but w does. Then v ∈ B and w ∈ A. The sum of the weights of all such pairs (v, w) of closed walks equals (1 · 1 · f_{n+2})(x · f_{n+3}) = xf_{n+3}f_{n+2}. Suppose neither v nor w begins with a loop. The total contribution by the corresponding pairs (v, w) is (1 · 1 · f_{n+2})(1 · 1 · f_{n+2}) = f_{n+2}^{2}.

Thus, when v, w ∈ A, the sum of the weights of such closed walks of length n + 3 is given by

S_{1} = x^{2}f_{n+3}^{2} + 2xf_{n+3}f_{n+2} + f_{n+2}^{2}.

Case 2. Suppose v ∈ A and w ∈ B. If v begins with a loop, then the sum of the weights of products of such closed walks of length n + 3 is (xf_{n+3})(f_{n+2}) = xf_{n+3}f_{n+2}. On the other hand, suppose v does not begin with a loop. The corresponding sum is (1 · 1 · f_{n+2})(f_{n+2}) = f_{n+2}^{2}. Consequently, the total contribution from this case is

S_{2} = xf_{n+3}f_{n+2} + f_{n+2}^{2}.

Case 3. Suppose v ∉ A, but w ∈ B. Then v ∈ B. If w begins with a loop, the resulting contribution is (f_{n+2})(xf_{n+3}) = xf_{n+3}f_{n+2}. If w does not begin with a loop, then the corresponding contribution is (f_{n+2})(1·1·f_{n+2}) = f_{n+2}^{2}. Consequently, the total contribution from Case 3 toward the cumulative sum is

S_{3} = xf_{n+3}f_{n+2} + f_{n+2}^{2}.

Case 4. Suppose v, w ∈ B. Clearly, the resulting contribution from this case toward S is

S_{4} = (f_{n+2})(f_{n+2}) = f_{n+2}^{2}.

Collecting all contributions from the four cases and using identities (2) and (3), we get

S = S_{1} + S_{2} + S_{3} + S_{4}
= x^{2}f_{n+3}^{2} + 4f_{n+2}^{2} + 4xf_{n+3}f_{n+2}
= l_{n+3}^{2},

as desired.

An Alternate Proof.

Proof. Alternatively, by focusing on the closed walks at v_{1} alone, we can establish identity (3). To see this, let C denote the set of closed walks of length n + 3 at v_{1}, and D that of length n + 1 at v_{1}. Let E = C ∪ D, where C ∩ D = ∅. The sum of the weights of the walks in E is f_{n+4} + f_{n+2} = l_{n+3}. Consequently, the sum S of the weights of elements in E × E is S = l_{n+3}^{2}.

We will now compute S in a different way. (In the interest of brevity, we highlight the key steps only.) To this end, let (v, w) be an arbitrary element in E × E.

Suppose v, w ∈ C. Then the sum of the weights of the pairs (v, w) of such closed walks is given by

S_{1} = x^{2}f_{n+3}^{2} + f_{n+2}^{2} + 2xf_{n+3}f_{n+2}.

On the other hand, let v ∈ C and w ∈ D. The total contribution from such pairs (v, w) is

S_{2} = x^{2}f_{n+3}^{2}f_{n+1} + xf_{n+3}f_{n} + xf_{n+2}f_{n+1} + f_{n+2}f_{n}
= f_{n+2}^{2} + xf_{n+3}f_{n+2}.

When v, w ∈ D, the total contribution from the corresponding pairs is

S_{3} = x^{2}f_{n+1}^{2} + 2xf_{n+1}f_{n} + f_{n}^{2}
= f_{n+2}^{2}.

Finally, let v ∈ D and w ∈ C. The corresponding contribution is

S_{4} = x^{2}f_{n+3}f_{n+1} + xf_{n+3}f_{n} + xf_{n+2}f_{n+1} + f_{n+2}f_{n}
= f_{n+2}^{2} + xf_{n+3}f_{n+2}.

Thus the cumulative sum S of the weights of all pairs (v, w) ∈ E × E is also given by

S_{1} + S_{2} + S_{3} + S_{4} = x^{2}f_{n+3}^{2} + 4f_{n+2}^{2} + 4xf_{n+3}f_{n+2}
= l_{n+3}^{2},

as expected.

Since [4, 14]

g_{n+1}^{2} + g_{n}^{2} = \begin{cases}f_{2n+1}, & if g_{n} = f_{n}; \\ (x^{2} + 4)f_{2n+1}, & if g_{n} = l_{n}; \end{cases}

these models also give a graph-theoretic interpretation of the identity [2, 4, 14]

g_{n+3}^{2} + g_{n}^{2} = (x^{2} + 1)(g_{n+2}^{2} + g_{n+1}^{2})
= \begin{cases}(x^{2} + 1)f_{2n+3}, & if g_{n} = f_{n}; \\ (x^{2} + 1)(x^{2} + 4)f_{2n+3}, & if g_{n} = l_{n}. \end{cases}

We now add that using the bijection algorithm in [11], we can translate the graphtheoretic models into tiling models with squares and dominoes, where weight(square) = x; weight(domino) = 1; and the weight of a tiling is the product of the weights of tiles in the tiling.

Replacing x with 2x in this discourse yields a graph-theoretic proof of the Pell-Lucas identity

q_{n+3}^{2} = 4x^{2}p_{n+3}^{2} + 4p_{n+2}^{2} + 8xp_{n+3}p_{n+2}
= p_{3}q_{n+2}^{2} + p_{3}q_{n+1}^{2} − q_{n}^{2}.

Finally, it follows from identity (4) that

F_{n+3}^{2} + 4F_{n+2}^{2} + 4F_{n+3}F_{n+2} = L_{n+3}^{2}.

Consequently, an L_{n+3} × L_{n+3} floor can be tessallated with nine tiles: one F_{n+3} × F_{n+3} tile; four F_{n+2} × F_{n+2} tiles; and four F_{n+3} × F_{n+2} tiles, where n ≥ 0.

5 Jacobsthal implications

Using the gibonacci-Jacobsthal relationships J_{n}(x) = x^{(n−1)/2}f_{n}(u) and j_{n}(x) = x^{n/2}l_{n}(u) [12], we can easily find the Jacobsthal counterparts of identities (2) and (3), where u = 1/\sqrt{x}:

c_{n+3}^{2} = J_{3}(x)c_{n+2}^{2} + xJ_{3}(x)c_{n+1}^{2} − x^{3}c_{n}^{2};  (5)
j_{n+1}^{2}(x) = J_{n+1}^{2}(x) + 4x^{2}J_{n}^{2}(x) + 4xJ_{n+1}(x)J_{n}(x),

respectively. (We have omitted the basic algebra for brevity and convenience.) Consequently,

C_{n+3}^{2} = 3C_{n+2}^{2} + 6C_{n+1}^{2} − 8C_{n}^{2};
j_{n+1}^{2} = J_{n+1}^{2} + 16J_{n}^{2} + 8J_{n+1}J_{n}.  (6)

Identity (6) implies that a j_{n+1} × j_{n+1} floor can be tiled with 25 tiles: one J_{n+1} × J_{n+1} tile; sixteen J_{n} × J_{n} tiles; and eight J_{n+1} × J_{n} tiles, where n ≥ 1.

5.1 A Jacobsthal digraph

Next we confirm independently identity (5) using graph-theoretic tools. To this end, we first present a weighted digraph D_{2}; see Figure 2. Its weighted adjacency matrix is

M = [\begin{matrix}1 & x \\ 1 & 0 \end{matrix}] .

Then

M^{n} = [\begin{matrix}J_{n+1}(x) & xJ_{n}(x) \\ J_{n}(x) & xJ_{n−1}(x) \end{matrix}] ,

where n ≥ 1; we can confirm this using induction.

Figure 2: Weighted digraph D_{2}

It then follows that the sum of the weights of closed walks of length n originating at v_{1} is J_{n+1}(x), and that of those originating at v_{2} is xJ_{n−1}(x). Consequently, the sum of all closed walks of length in the digraph D_{2} is J_{n+1}(x) + xJ_{n−1}(x) = j_{n}(x). These facts play a central role in the graph-theoretic proof.

With these tools at our finger tips, we now present the proof of each part.

Proof.

Part 1. To establish part 1, we let A be the set of closed walks of length n + 2 starting at v_{1}. The sum of the weights of all such closed walks is J_{n+3}(x); so the sum S of the weights of all ordered pairs (v, w) ∈ A × A is J_{n+3}^{2}(x).

We will now compute S in a different way. Again, let (v, w) be an arbitrary element of A×A. Suppose both v and w begin with a loop; the sum of the weights of such pairs (v, w) is [1·J_{n+2}(x)][1·J_{n+2}(x)] = J_{n+2}^{2}(x). If v begins with a loop and w does not, the corresponding sum is [1 · J_{n+2}(x)][x · 1 · J_{n+1}(x)] = xJ_{n+2}(x)J_{n+1}(x). Suppose v does not begin with a loop, but w does; then also the resulting sum is [x · 1 · J_{n+1}(x)][1 · J_{n+2}(x)] = xJ_{n+2}(x)J_{n+1}(x).

Finally, if both v and w do not begin with a loop, the contribution from such pairs equals [x · 1 · J_{n+1}(x)][x · 1 · J_{n+1}(x)] = x^{2}J_{n+1}^{2}(x).

Thus the cumulative contribution of pairs (v, w) all closed walks of length n + 2 starting at v_{1} is given by

S = J_{n+2}^{2}(x) + 2xJ_{n+2}(x)J_{n+1}(x) + x^{2}J_{n+1}^{2}(x)
= J_{n+2}^{2}(x) + xJ_{n+2}(x)[J_{n+2}(x) − xJ_{n}(x)] + xJ_{n+1}(x)[J_{n+1}(x) + xJ_{n}(x)] + x^{2}J_{n+1}^{2}(x)
= (x + 1)J_{n+2}^{2}(x) + x(x + 1)J_{n+1}^{2}(x) − x^{2}J_{n}(x)[J_{n+2}(x) − J_{n+1}(x)]
= (x + 1)J_{n+2}^{2}(x) + x(x + 1)J_{n+1}^{2}(x) − x^{3}J_{n}(x).

Combining the two values of S yields identity (5) when c_{n} = J_{n}(x).

Part 2. To confirm identity (5) when c_{n} = j_{n}(x), we focus on the closed walks of lengths n + 3 and n in the digraph. Let C be the set of closed walks of length n + 3 starting at v_{1}, and D the set of those starting at v_{2}. Clearly, C ∩ D = ∅, so the sum of the weights of the walks in F = C ∪ D is j_{n+3}(x). Consequently, the sum S_{1} of the weights of the ordered pairs (v, w) ∈ F × F is j_{n+3}^{2}(x).

Now let R denote the set of closed walks of length n originating at v_{1}, and S that of those originating at v_{2}. It follows by the preceding argument that the sum S_{2} of the weights of the ordered pairs (v, w) ∈ G × G is j_{n}^{2}(x), where G = R ∪ S and R ∩ S = ∅.

Thus

S_{1} + x^{3}S_{2} = j_{n+3}^{2}(x) + x^{3}j_{n}^{2}(x).

We will now compute the sum S_{1} + x^{3}S_{2} in a different way. Again, let (v, w) be an arbitrary element of F × F.

Suppose v, w ∈ C. Then the sum of the weights of pairs (v, w) of such closed walks of length n + 3 originating at v_{1} is [J_{n+4}(x)][J_{n+4}(x)] = J_{n+4}^{2}(x). If v ∈ C and w ∈ D, then the resulting sum is [J_{n+4}(x)][xJ_{n+2}(x) = xJ_{n+4}(x)J_{n+2}(x). When v ∈ D and w ∈ C, the corresponding sum is [xJ_{n+2}(x)][J_{n+4}(x)] = xJ_{n+4}(x)J_{n+2}(x). Finally, when v, w ∈ D, the contribution from such pairs (v, w) is [xJ_{n+2}(x)][xJ_{n+2}(x)] = x^{2}J_{n+2}^{2}(x). Thus

S_{1} = J_{n+4}^{2}(x) + 2xJ_{n+4}(x)J_{n+2}(x) + x^{2}J_{n+2}^{2}(x).

It then follows that

S_{2} = J_{n+1}^{2}(x) + 2xJ_{n+1}(x)J_{n−1}(x) + x^{2}J_{n−1}^{2}(x).

Consequently, S_{1} + x^{3}S_{2} = A + B, where

A = J_{n+4}^{2}(x) + x^{2}J_{n+2}^{2}(x) + x^{3}J_{n+1}^{2}(x);
B = x^{5}J_{n−1}^{2}(x) + 2xJ_{n+4}(x)J_{n+2}(x) + 2x^{4}J_{n+1}(x)J_{n−1}(x).

Proof. We will now confirm that S_{1} + x^{3}S_{2} = (x + 1)j_{n+2}^{2}(x) + x(x + 1)j_{n+1}^{2}(x). The proof involves a lot of carefully prepared basic algebra; so in the interest of brevity, clarity, and convenience, we present only the major steps; also we omit the argument in the functional notation.

We have

A = (J_{n+3} + xJ_{n+2})^{2} + x^{2}J_{n+2}^{2} + x^{3}J_{n+1}^{2}
= J_{n+3}^{2} + 2x^{2}J_{n+2}^{2} + 2xJ_{n+2}(J_{n+2} + xJ_{n+1}) + x^{3}J_{n+1}^{2}
= J_{n+3}^{2} + (x^{2} + x)J_{n+2}^{2} + x^{3}J_{n+1}^{2} + (x^{2} + x)J_{n+2}^{2} + 2x^{2}J_{n+2}J_{n+1}
= J_{n+3}^{2} + (x^{2} + x)J_{n+2}^{2} + x^{3}J_{n+1}^{2} + (x^{2} + x)J_{n+2}^{2} + 2x^{2}J_{n+1}(J_{n+3} − xJ_{n+1})
= J_{n+3}^{2} + (x^{2} + x)J_{n+2}^{2} + x^{3}J_{n+1}^{2} + (x^{2} + x)J_{n+2}^{2} + 2x^{2}J_{n+3}J_{n+1} − 2x^{3}J_{n+1}^{2};
B = x^{3}(J_{n+1} − J_{n})^{2} + 2xJ_{n+2}(J_{n+3} + xJ_{n+2}) + 2x^{3}J_{n+1}(J_{n+1} − J_{n})
= x^{3}J_{n+1}^{2} + x^{3}J_{n}^{2} − 2x^{3}J_{n+1}J_{n} + 2xJ_{n+3}J_{n+2} + 2x^{2}J_{n+2}^{2} + 2x^{3}J_{n+1}^{2} − 2x^{3}J_{n+1}J_{n}
= x^{3}J_{n+1}^{2} + x^{3}J_{n}^{2} − 2x^{3}J_{n+1}J_{n} + 2xJ_{n+3}(J_{n+1} + xJ_{n}) + 2x^{2}J_{n+2}^{2} + 2x^{3}J_{n+1}^{2} − 2x^{3}J_{n+1}J_{n}
= 2xJ_{n+3}J_{n+1} + x^{3}J_{n}^{2} + 2x^{3}J_{n+1}J_{n} + 2x^{2}J_{n+2}^{2} + 3x^{3}J_{n+1}^{2} − 4x^{3}J_{n+1}J_{n}
= 2xJ_{n+3}J_{n+1} + x^{3}J_{n}^{2} + 2x^{2}J_{n}(J_{n+2} + xJ_{n+1}) + x(J_{n+3} − J_{n+2})^{2} + +2x^{2}J_{n+2}^{2} + 2x^{3}J_{n+1}^{2}

− 4x^{3}J_{n+1}J_{n}

= 2xJ_{n+3}J_{n+1} + x^{3}J_{n}^{2} + 2x^{2}J_{n+2}J_{n} + xJ_{n+3}^{2} + 2x^{3}J_{n+1}J_{n} + (2x^{2} + x)J_{n+2}^{2} − 2xJ_{n+3}J_{n+2}

+ 2x^{3}J_{n+1}^{2} − 4x^{3}J_{n+1}J_{n}.

Then

S_{1} + x^{3}S_{2} = C + D + (x^{2} + x)J_{n+2}^{2} − 2x^{3}J_{n+1}J_{n} + (2x^{2} + x)J_{n+2}^{2} − 2xJ_{n+3}J_{n+2},

where

C = (x + 1)(J_{n+3}^{2} + 2xJ_{n+3}J_{n+1}) + x^{3}J_{n+1}^{2}
= (x + 1)(J_{n+3} + xJ_{n+1})^{2} − x^{2}J_{n+1}^{2}
= (x + 1)j_{n+2}^{2} − x^{2}J_{n+1}^{2};
D = (x^{2} + x)J_{n+2}^{2} + x^{3}J_{n}^{2} + 2x^{2}J_{n+2}J_{n}
= (x^{2} + x)(J_{n+2} + xJ_{n})^{2} − 2x^{3}J_{n+2}J_{n} − x^{4}J_{n}^{2}
= x(x + 1)j_{n+1}^{2} − 2x^{3}J_{n+2}J_{n} − x^{4}J_{n}^{2}.

Consequently,

S_{1} + x^{3}S_{2} = (x + 1)j_{n+2}^{2} + x(x + 1)j_{n+1}^{2} + E,

where

E = −2x^{3}J_{n+1}J_{n} − 2x^{2}J_{n+2}J_{n+1} − 2x^{4}J_{n}^{2} + 2x^{2}J_{n+2}^{2}
= −2x^{3}J_{n}(J_{n+1} + xJ_{n}) + 2x^{2}J_{n+2}(J_{n+2} − J_{n+1})
= −2x^{3}J_{n+2}J_{n} + 2x^{3}J_{n+2}J_{n}
= 0.

Thus

S_{1} + x^{3}S_{2} = (x + 1)j_{n+2}^{2} + x(x + 1)j_{n+1}^{2},

as expected.

6 Acknowledgments

The author would like to thank the reviewer for his/her constructive suggestions for improving the quality of exposition of the original version.

References

[1] C. Alsina and R. B. Nelsen, Charming Proofs: A Journey Into Elegant Mathematics, MAA, 2010.

[2] T. Amdeberhan, X. Chen, V. H. Moll, and B. E. Sagan, Generalized Fibonacci polynomials and Fibonomial coefficients, Ann. Comb. 18 (2014), 541–562.

[3] M. Bicknell, A primer for the Fibonacci numbers: Part VII, Fibonacci Quart. 8 (1970), 407–420.

[4] R. Flórez, N. McAnally, and A. Mukherjee, Identities for the generalized Fibonacci polynomial, Integers, 18B (2018), Article A2.

[5] A. F. Horadam, Jacobsthal representation numbers, Fibonacci Quart. 34 (1996), 40–54.

[6] A. F. Horadam, Jacobsthal representation polynomials, Fibonacci Quart. 35 (1997), 137–148.

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

[8] H. W. Gould, Problem B-7, Fibonacci Quart. 1 (1963), 80.

[9] T. Koshy, Discrete Mathematics with Applications, Elsevier, 2004.

[10] T. Koshy, Pell and Pell-Lucas Numbers with Applications, Springer, 2014.

[11] T. Koshy, Graph-theoretic models for the univariate Fibonacci family, Fibonacci Quart. 53 (2015), 135–146.

[12] T. Koshy, Polynomial extensions of the Lucas and Ginsburg identities revisited, Fibonacci Quart. 55 (2017), 147–151.

[13] T. Koshy, Fibonacci and Lucas Numbers with Applications, Volume I, Second Edition, Wiley, 2018.

[14] T. Koshy, Fibonacci and Lucas Numbers with Applications, Volume II, Wiley, 2019.

2010 Mathematics Subject Classification: Primary 05A19; Secondary 11B37, 11B39, 11Cxx. Keywords: Fibonacci number, Lucas number, Pell number, Pell-Lucas number, Jacobsthal number, Jacobsthal-Lucas number, Q-matrix, weight, weighted digraph, weighted adjacency matrix, walk.

(Concerned with sequences \underline{A000032}, \underline{A000045}, \underline{A000129}, \underline{A001045}, \underline{A002203}, and \underline{A014551}.)

Received June 1 2018; revised versions received August 24 2018; February 24 2019; February 25 2019. Published in Journal of Integer Sequences, May 22 2019.

Return to Journal of Integer Sequences home page.