A Combinatorial Proof for the Generating Function of Powers of a Second-Order Recurrence Sequence

Yifan Zhang and George Grossman Department of Mathematics Central Michigan University Mount Pleasant, MI 48858 USA

                       zhang5y@cmich.edu
                      gross1gw@cmich.edu

Abstract In this paper, we derive a formula for the generating function of powers of a secondorder linear recurrence sequence, with initial conditions 0 and 1. As an example, we find the generating function of the powers of the nonnegative integers. We also find new formulas for computing Eulerian polynomials.

1 Introduction

Second-order linear recurrence sequences have been studied for hundreds of years. One of the earlier historical summaries was done by Dickson [1, Vol. 1, Chapter 17, pp. 393–411].

In the present paper, we use the notation W_{n;(a,b;p,q)} to define the second-order linear recurrence sequence,

W_{n+2;(a,b;p,q)} = pW_{n+1;(a,b;p,q)} + qW_{n;(a,b;p,q)},

having initial conditions

W_{0;(a,b;p,q)} = a, W_{1;(a,b;p,q)} = b.

Example 1. The nonnegative integers are represented by W_{n;(0,1;2,−1)}.

Domino tiling methods have been used to find combinatorial identities and recurrence relations of certain sequences. Sellers [6] proved that the number of domino tilings of the graph W_{4}×P_{n−1} equals F_{n}P_{n} (sequence \underline{A001582} in Sloane’s On-Line Encyclopedia of Integer Sequences [7]), which is the product of the n-th Fibonacci number and the n-th Pell number. Katz and Stenson [3] considered the number of tilings of a (2 × n)-board \underline{A030186}.

Let F_{k}(x) be the generating function for the k-th powers of the Fibonacci numbers, defined by

F_{k}(x) = ∑_{n=0}^{∞} F_{n}^{k}x^{n}, k ∈ ℕ^{+}.

For 1 ≤ k ≤ 10, F_{k}(x) can be found respectively from \underline{A000045}, \underline{A007598}, \underline{A056570}, \underline{A056571}, \underline{A056572}, \underline{A056573}, \underline{A056574}, \underline{A056585}, \underline{A056586}, and \underline{A056587} in Sloane’s On-Line Encyclopedia of Integer Sequences [7] (OEIS).

In 1962, Riordan [5] gave the following recurrence relation,

(1 − L_{k}(x) + (−1)^{k}x^{2})F_{k}(x) = 1 + kx ∑_{j=1}^{⌊ \frac{k}{2} ⌋}(−1)^{j} \frac{A_{kj}}{j} F_{k−2j} ((−1)^{j}x) ,

where L_{k} is the k-th Lucas number \underline{A000032}. In 1999, Dujella [2] showed the doubly-indexed sequence A_{kj}, has generating function given by,

(1 − x − x^{2})^{−j} = ∑_{k=2j}^{∞} A_{kj}x^{k−2j}, j ≥ 0.

In 2003, Stănică [8] obtained a closed form for generating function of the non-degenerate second-order recurrence relation,

U_{n+2} = aU_{n+1} + bU_{n}, a, b, U_{0}, U_{1} ∈ ℤ,

such that δ = a^{2} + 4b ≠ 0. Let α = \frac{1}{2}(a + \sqrt{a^{2} + 4b}), β = \frac{1}{2}(a − \sqrt{a^{2} + 4b}) and A = \frac{U_{1}−U_{0}β}{α−β}, B = \frac{U_{1}−U_{0}α}{α−β}, V_{n} = α^{n} +β^{n} with initial conditions V_{0} = 2, V_{1} = a, and let U_{k}(x) = ∑_{i=0}^{∞} U_{i}^{k}x^{i}.

If k is odd, then

U_{k}(x) = ∑_{j=0}^{\frac{k−1}{2}}(−AB)^{j}\binom{k}{j}\frac{A^{k−2j} − B^{k−2j} + (−b)^{j}((Bα)^{k−2j} − (Aβ)^{k−2j})x}{1 − (−b)^{j}V_{k−2j}x − b^{k}x^{2}}.

If k is even, then

U_{k}(x) = ∑_{j=0}^{\frac{k}{2} −1}(−AB)^{j}\binom{k}{j}\frac{B^{k−2j} + A^{k−2j} − (−b)^{j}((Bα)^{k−2j} + (Aβ)^{k−2j})x}{1 − (−b)^{j}V_{k−2j}x + b^{k}x^{2}} + \binom{k}{\frac{k}{2}} \frac{(−AB)^{\frac{k}{2}}}{1 − (−b)^{\frac{k}{2}} x}.

In 2004, Mansour [4] obtained a formula for the generating functions of powers of secondorder recurrence sequence in terms of the determinants of certain matrices, given by

W_{n;(a,b;p,q)}(x) = \frac{det(δ_{k})}{det(Δ_{k})},

where

Δ_{k} = [\begin{matrix}A_{1×1} & C_{1×(k−1)} \\ B_{(k−1)×1} & D_{(k−1)×(k−1)} \end{matrix}]

δ_{k} = [\begin{matrix}E_{1×1} & C_{1×(k−1)} \\ F_{(k−1)×1} & D_{(k−1)×(k−1)} \end{matrix}]
A_{1×1} = [1 − p^{k}x − q^{k}x^{2}]
E_{1×1} = [a^{k} + g_{k}x] ,
B_{(k−1)×1} = [−p^{k−1}x −p^{k−2}x ⋯ −p^{1}x]^{T}
F_{(k−1)×1} = [g_{k−1}x g_{k−2}x ⋯ g_{1}x]^{T} ,
C_{1×(k−1)} = [−xp^{k−1}q^{1}\binom{k}{1} −xp^{k−2}q^{2}\binom{k}{2} ⋯ −xp^{1}q^{k−1}\binom{k}{k−1}] ,

D_{(k−1)×(k−1)} = [\begin{matrix}1 − xp^{k−2}q^{1}\binom{k−1}{1} & −xp^{k−3}q^{2}\binom{k−1}{2} & ⋯ & −xq^{k−1}\binom{k−1}{k−1} \\ −xp^{k−3}q^{1}\binom{k−2}{1} & 1 − xp^{k−4}q^{2}\binom{k−2}{2} & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ −xq^{1}\binom{1}{1} & 0 & ⋯ & 1 \end{matrix}] ,

with g_{j} = (b^{j} − a^{j}p^{j})a^{k−j}, j = 1, 2, …, k.

In 2017, Zhang and Grossman [9] used a counting method to relate the number of tilings of a (k × n)-board to the generating function of the k-th power of the Fibonacci numbers.

In the present paper, we extend the previous result to the generating function of the k-th power of an arbitrary second-order linear recurrence sequence having initial conditions 0 and 1.

Eulerian polynomials, denoted in the present paper by A_{k}(x), were introduced by Euler in 1755 and can be determined from the identity

∑_{n=0}^{∞} n^{k}x^{n} = \frac{xA_{k}(x)}{(1 − x)^{k+1}} .

The coefficients of Eulerian polynomials leads to the Eulerian numbers \underline{A008292}. The recurrence relation for nonnegative integers denoted a_{n}, n ≥ 0 is given by

a_{n+2} = 2a_{n+1} − a_{n}, a_{0} = 0, a_{1} = 1.

In the next section we derive an expression for powers of W_{n;(0,1;p,q)} with arbitrary p ≠ 0, q. Sequences associated with such generating functions are Pell, Jacobsthal and the nonnegative integers. Closed-form expressions for Eulerian polynomials are also given in Corollary 23 and Remark 26.

2 Closed form for 𝒲_{k;(0,1;p,q)}(x)

The Fibonacci number F_{n+1} gives the number of ways that 1 × 2 dominoes and squares can cover a 1 × n checkerboard. We begin with a series of definitions.

Definition 2. Let 𝒲_{k;(0,1;p,q)}(x) = ∑_{n=0}^{∞} W_{n}^{k}x^{n} be the generating function of k-th power of W_{n} where W_{n+2} = pW_{n+1} + qW_{n} with initial conditions W_{0} = 0 and W_{1} = 1 with p, q ∈ ℝ, p ≠ 0.

In this section, we use the notation (p, q) in the place of (0, 1; p, q).

Definition 3. For k ≥ 1 and n ≥ 1, let F_{k×n;(p,q)} denote the Fibonacci (k × n; (p, q)) checkerboard, which is a checkerboard (or simply, board) with height k and length n, covered by squares and dominoes, such that the dominoes can only be placed horizontally. Let F_{k×n;(p,q)} be the set of all F_{k×n;(p,q)} boards. Define a function V: F_{k×n;(p,q)} → ℝ (value of F_{k×n;(p,q)}) by V (F_{k×n;(p,q)}) = p^{s}q^{d}, where d and s denote the number of dominoes and squares respectively in this F_{k×n;(p,q)} board. Let us also redefine the function V: 2^{F_{k×n;(p,q)}} → ℝ by V (A) = ∑_{a∈A} V (a). Let w_{k×n;(p,q)} = V (F_{k×n;(p,q)}) be the sum of all the values of the different F_{k×n;(p,q)} boards.

Note that each F_{k×n;(p,q)} board is comprised of k F_{1×n;(p,q)} boards (horizontal layers), each of which has at most n components consisting of dominoes and squares.

We define w_{k×(−1);(p,q)} = 0 and w_{k×0;(p,q)} = 1 for k ∈ ℕ^{+}.

Definition 4. The Fibonacci (k × n; (p, q)) minimal checkerboard called an M_{k×n;(p,q)} board, is an F_{k×n;(p,q)} board which cannot be vertically divided into two Fibonacci checkerboards. Let M_{k×n;(p,q)} be the set of all M_{k×n;(p,q)} boards. Let m_{k×n;(p,q)} = V (M_{k×n;(p,q)}) be the sum of all the values of the different M_{k×n;(p,q)} boards.

Note that M_{k×n;(p,q)} ⊆ F_{k×n;(p,q)}.

Example 5. There are total of nine different F_{2×3;(p,q)} boards shown in Figure 1. We find that w_{2×3;(p,q)} = p^{6}+4p^{4}q+4p^{2}q^{2}. There are two different M_{2×3;(p,q)} boards and m_{2×3;(p,q)} = 2p^{2}q^{2}.

Lemma 6. For n ≥ 1 and k ≥ 1, w_{1×n;(p,q)} = W_{n+1;(p,q)} and w_{k×n;(p,q)} = W_{n+1;(p,q)}^{k}.

Proof. This lemma can be proven inductively.

If n = 1, then w_{1×1;(p,q)} = p = W_{2;(p,q)}. If n = 2, then w_{1×2;(p,q)} = p^{2} + q = W_{3;(p,q)}.

M_{2×(1,1,1);(p,q)}  M_{2×(1,2);(p,q)}  M_{2×(2,1);(p,q)}

M_{2×(1,2);(p,q)}  M_{2×(2,1);(p,q)}  M_{2×(1,2);(p,q)}

S_{1,2×3;(p,q)}  S_{1,2×3;(p,q)}  M_{2×(2,1);(p,q)}

Figure 1: Nine F_{2×3;(p,q)} boards.

If w_{1×n;(p,q)} = W_{n+1;(p,q)} and w_{1×(n+1);(p,q)} = W_{n+2;(p,q)} hold, then

w_{1×(n+2);(p,q)} = pw_{1×(n+1);(p,q)} + qw_{1×n;(p,q)} = pW_{n+2;(p,q)} + qW_{n+1;(p,q)} = W_{n+3;(p,q)}.

Therefore w_{1×n;(p,q)} = W_{n+1;(p,q)} for n ≥ 1.

We know that the F_{k×n;(p,q)} board has k independent layers. Also, each independent layer is an F_{1×n;(p,q)} board which implies that the sum of all the values of each layer is w_{1×n;(p,q)}. Therefore, we can conclude that w_{k×n;(p,q)} = W_{n+1;(p,q)}^{k}.

The generating function for powers of Pell numbers (\underline{A000129}, \underline{A079291}, \underline{A110272}) is denoted P_{k}(x) = 𝒲_{k;(2,1)}(x); powers of Jacobsthal numbers (\underline{A001045}, \underline{A139818}), is denoted by J_{k}(x) = 𝒲_{k;(1,2)}(x); and powers of nonnegative integers (\underline{A001477}, \underline{A000290}, \underline{A000578}, \underline{A000583}, \underline{A000584}, \underline{A001014}, \underline{A001015}, \underline{A001016}, \underline{A001017}, and \underline{A008454}), is denoted by 𝒲_{k;(2,−1)}(x).

In Table 1 we listed values of m_{4×n;(2,−1)} for 1 ≤ n ≤ 7. The smaller values were obtained by direct calculation, larger values were computed using Lemma 19. These values will be used to explain Example 10 and Example 12.

Remark 7. Any non-minimal F_{k×n;(p,q)} board can be split uniquely into at most n Fibonacci minimal boards. Specifically, there exist j, 1 < j ≤ n, and an ordered partition n_{1} + n_{2} + ⋯ + n_{j} = n, such that the F_{k×n;(p,q)} board can be split into M_{k×n_{1};(p,q)}, M_{k×n_{2};(p,q)}, …, M_{k×n_{j};(p,q)} boards (from left to right).

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ m_{4×n;(2,−1)} & 16 & −175 & 1760 & −17456 & 172832 & −1710896 & 16936160 \end{matrix}

Table 1: m_{4×n;(2,−1)} for 1 ≤ n ≤ 7.

Definition 8. Let an M_{k×(n_{1},n_{2},...,n_{j});(p,q)} board be an F_{k×n;(p,q)} board with n_{1}+n_{2}+⋯+n_{j} = n that can be split into M_{k×n_{1};(p,q)}, M_{k×n_{2};(p,q)}, …, M_{k×n_{j};(p,q)} boards. Let M_{k×(n_{1},n_{2},...,n_{j});(p,q)} be the set of all different M_{k×(n_{1},n_{2},...,n_{j});(p,q)} boards. Let

m_{k×(n_{1},n_{2},...,n_{j});(p,q)} = V (M_{k×(n_{1},n_{2},...,n_{j});(p,q)})

be the sum of all the values of the different M_{k×(n_{1},n_{2},...,n_{j});(p,q)} boards.

The value of m_{k×(n_{1},n_{2},...,n_{j});(p,q)} is quantified in Lemma 9. Note that there are two examples in Figure 1.

Lemma 9. For k ≥ 1 and n ≥ 1, n_{i} ∈ ℕ^{+} for i ∈ {1, 2, …, j} we have,

m_{k×(n_{1},n_{2},...,n_{j});(p,q)} = ∏_{i=1}^{j} m_{k×n_{i};(p,q)},

and

W_{n+1;(p,q)}^{k} = ∑_{j=1}^{n} ∑_{n_{1}+n_{2}+···+n_{j}=n} ∏_{i=1}^{j} m_{k×n_{i};(p,q)}.

Proof. Since an M_{k×(n_{1},n_{2},...,n_{j});(p,q)} board is the combination of M_{k×n_{1};(p,q)}, M_{k×n_{2};(p,q)}, …, M_{k×n_{j};(p,q)} boards, we have m_{k×(n_{1},n_{2},...,n_{j});(p,q)} = ∏_{i=1}^{j} m_{k×n_{i};(p,q)}.

From Remark 7, each F_{k×n;(p,q)} board is either an M_{k×n;(p,q)} board or can be uniquely divided into j minimal boards where 2 ≤ j ≤ n. Then the set

{M_{k×n;(p,q)}, ⋃_{n_{1}+n_{2}=n} M_{k×(n_{1},n_{2});(p,q)}, …, ⋃_{n_{1}+n_{2}+···+n_{n}=n} M_{k×(n_{1},n_{2},...,n_{n});(p,q)}}

forms a partition of F_{k×n;(p,q)}. That is,

F_{k×n;(p,q)} = M_{k×n;(p,q)} ⋃ ( ⋃_{n_{1}+n_{2}=n} M_{k×(n_{1},n_{2});(p,q)}) ⋃ ⋯ ⋃ ( ⋃_{n_{1}+n_{2}+···+n_{n}=n} M_{k×(n_{1},n_{2},...,n_{n});(p,q)}) .

Therefore, from Lemma 6,

W_{n+1;(p,q)}^{k} = w_{k×n;(p,q)}
= V (F_{k×n;(p,q)})
= V (M_{k×n;(p,q)}) + V ( ⋃_{n_{1}+n_{2}=n} M_{k×(n_{1},n_{2});(p,q)}) + ⋯

+V ( ⋃_{n_{1}+n_{2}+···+n_{n}=n} M_{k×(n_{1},n_{2},...,n_{n});(p,q)})

= m_{k×n;(p,q)} + ∑_{n_{1}+n_{2}=n} m_{k×(n_{1},n_{2});(p,q)} + ⋯ + ∑_{n_{1}+n_{2}+···+n_{n}=n} m_{k×(n_{1},n_{2},...,n_{n});(p,q)}

= m_{k×n;(p,q)} + ∑_{n_{1}+n_{2}=n} ∏_{i=1}^{2} m_{k×n_{i};(p,q)} + ⋯ + ∑_{n_{1}+n_{2}+···+n_{n}=n} ∏_{i=1}^{n} m_{k×n_{i};(p,q)}

= ∑_{j=1}^{n} ∑_{n_{1}+n_{2}+···+n_{j}=n} ∏_{i=1}^{j} m_{k×n_{i};(p,q)}.

Example 10.

W_{4;(2,−1)}^{4} = m_{4×3;(2,−1)} + m_{4×(2,1);(2,−1)} + m_{4×(1,2);(2,−1)} + m_{4×(1,1,1);(2,−1)}
= 1760 + (−175) · 16 + 16 · (−175) + 16 · 16 · 16
= 256
= 4^{4}.

Lemma 11. For k ∈ ℕ^{+}, let e_{k;(p,q)} = ∑_{n=1}^{∞} m_{k×n;(p,q)}x^{n}. Then,

𝒲_{k;(p,q)}(x) = \frac{x}{1 − e_{k;(p,q)}} .

Proof. For k, n ∈ ℕ^{+}, the coefficient of x^{n} in e_{k;(p,q)} + e_{k;(p,q)}^{2} + ⋯ + e_{k;(p,q)}^{n} + ⋯ is

m_{k×n;(p,q)} + ∑_{\begin{matrix}n_{1}+n_{2}=n \\ n_{i}∈ℕ^{+} \end{matrix}} ∏_{i=1}^{2} m_{k×n_{i};(p,q)} + ∑_{\begin{matrix}n_{1}+n_{2}+n_{3}=n \\ n_{i}∈ℕ^{+} \end{matrix}} ∏_{i=1}^{3} m_{k×n_{i};(p,q)} + ⋯

+ ∑_{\begin{matrix}n_{1}+n_{2}+···+n_{n}=n \\ n_{i}∈ℕ^{+} \end{matrix}} ∏_{i=1}^{n} m_{k×n_{i};(p,q)}

= ∑_{j=1}^{n} ∑_{\begin{matrix}n_{1}+n_{2}+···+n_{j}=n \\ n_{i}∈ℕ^{+} \end{matrix}} ∏_{i=1}^{j} m_{k×n_{i};(p,q)}.

Also, e_{k;(p,q)} + e_{k;(p,q)}^{2} + ⋯ + e_{k;(p,q)}^{n} + ⋯ = \frac{1}{1−e_{k;(p,q)}} − 1. Therefore,

∑_{n=1}^{∞} ((∑_{j=1}^{n} ∑_{\begin{matrix}n_{1}+n_{2}+···+n_{j}=n \\ n_{i}∈ℕ^{+} \end{matrix}} ∏_{i=1}^{j} m_{k×n_{i};(p,q)}) x^{n}) = \frac{1}{1 − e_{k;(p,q)}} − 1.

Employing Lemmas 6 and 9, we obtain,

𝒲_{k;(p,q)}(x) = ∑_{n=0}^{∞} W_{n;(p,q)}^{k}x^{n}

= W_{0;(p,q)}^{k} + W_{1;(p,q)}^{k}x + ∑_{n=2}^{∞} W_{n;(p,q)}^{k}x^{n}

= x + ∑_{n=1}^{∞} W_{n+1;(p,q)}^{k}x^{n+1}

= x + x ∑_{n=1}^{∞} W_{n+1;(p,q)}^{k}x^{n}

= x + x ∑_{n=1}^{∞} ((∑_{j=1}^{n} ∑_{\begin{matrix}n_{1}+n_{2}+···+n_{j}=n \\ n_{i}∈ℕ^{+} \end{matrix}} ∏_{i=1}^{j} m_{k×n_{i};(p,q)}) x^{n})

= x + x (\frac{1}{1 − e_{k;(p,q)}} − 1)
= \frac{x}{1 − e_{k;(p,q)}} .

Example 12. From Table 1, we have e_{4;(2,−1)} = ∑_{n=1}^{∞} m_{4×n;(2,−1)}x^{n} = 16x−175x^{2}+1760x^{3}− ⋯ and 𝒲_{4;(2,−1)}(x) = \frac{x}{1−e_{4;(2,−1)}} .

Now we determine the closed form of e_{k;(p,q)}.

Lemma 13. Suppose S_{1,n}, S_{2,n}, …, S_{m,n} are real-valued sequences such that S_{i,n+1} = ∑_{j=1}^{m} a_{i,j}S_{j,n} for 1 ≤ i ≤ m and n ≥ 0.

Let [a_{i,j}]_{m×m} = [\begin{matrix}a_{1,1} & a_{1,2} & ⋯ & a_{1,m} \\ a_{2,1} & a_{2,2} & ⋯ & a_{2,m} \\ ⋮ & ⋮ & ... & ⋮ \\ a_{m,1} & a_{m,2} & ⋯ & a_{m,m} \end{matrix}]_{m×m}, [S_{j,n}]_{m×1} = [ S_{1,n} ; S_{2,n} ; ⋮ ; S_{m,n}]_{m×1}, B_{m+1} = [1 1 ⋮ 1]_{1×m}^{T}.

Then ∑_{j=1}^{m} S_{j,n} = B_{m+1}[a_{i,j}]_{m×m}^{n−l}[S_{j,l}]_{m×1}.

Proof. Since

[a_{i,j}]_{m×m}^{n−l}[S_{j,l}]_{m×1} = [a_{i,j}]_{m×m}^{n−l−1}[a_{i,j}]_{m×m}[S_{j,l}]_{m×1} = [a_{i,j}]_{m×m}^{n−l−1}[S_{j,l+1}]_{m×1} = ⋯ = [S_{j,n}]_{m×1},

then

∑_{j=1}^{m} S_{j,n} = B_{m+1}[S_{j,n}]_{m×1} = B_{m+1}[a_{i,j}]_{m×m}^{n−l}[S_{j,l}]_{m×1}.

Definition 14. Let an S_{j,k×n;(p,q)} board (j ∈ {1, 2, 3, …, k}, n ≥ 2) be an M_{k×n;(p,q)} board with j dominoes in last two columns. Let S_{j,k×n;(p,q)} be the set of all S_{j,k×n;(p,q)} boards. Let s_{j,k×n;(p,q)} = V (S_{j,k×n;(p,q)}) be the sum of all the values of the different S_{j,k×n;(p,q)} boards.

Example 15. In Figure 2, the board on the left is an S_{1,4×5;(p,q)} board and the board on the right is a combination of an S_{1,4×3;(p,q)} board and an S_{2,4×2;(p,q)} board.

M_{4×5;(p,q)}, also S_{1,4×5;(p,q)}  M_{4×(3,2);(p,q)}

Figure 2: Two different boards.

Lemma 16. For k ∈ ℕ^{+}, s_{j,k×2;(p,q)} = p^{2(k−j)}q^{j}\binom{k}{j} for 1 ≤ j ≤ k and

m_{k×n;(p,q)} = \begin{cases}p^{k}, & if n = 1; \\ q^{k} + ∑_{j=1}^{k−1} s_{j,k×2;(p,q)}, & if n = 2; \\ ∑_{j=1}^{k−1} s_{j,k×n;(p,q)}, & if n ≥ 3. \end{cases}

Proof. For n ≥ 3, S_{1,k×n;(p,q)}, S_{2,k×n;(p,q)}, …, S_{k−1,k×n;(p,q)} forms a partition of M_{k×n;(p,q)}. Therefore,

m_{k×n;(p,q)} = V (M_{k×n;(p,q)}) = ∑_{j=1}^{k−1} V (S_{j,k×n;(p,q)}) = ∑_{j=1}^{k−1} s_{j,k×n;(p,q)}.

For n = 2 and j = k, there is only one S_{k,k×2;(p,q)} board and V (S_{k,k×2;(p,q)}) = q^{k}. For 1 ≤ j ≤ k − 1, there are \binom{k}{j} different S_{j,k×2;(p,q)} boards. Then s_{j,k×2;(p,q)} = p^{2(k−j)}q^{j}\binom{k}{j}. Therefore,

m_{k×2;(p,q)} = q^{k} + ∑_{j=1}^{k−1} s_{j,k×2;(p,q)} = q^{k} + ∑_{j=1}^{k−1} p^{2(k−j)}q^{j}\binom{k}{j}.

Lemma 17. For n ≥ 2 and 1 ≤ j ≤ k − 1,

s_{j,k×(n+1);(p,q)} = ∑_{i=1}^{k−j} p^{k−2j}q^{j}\binom{k − i}{j}s_{i,k×n;(p,q)}.

Proof. An S_{j,k×(n+1);(p,q)} board, 1 ≤ j ≤ k − 1, can be obtained from an S_{i,k×n;(p,q)} board, 1 ≤ i ≤ k − j, by the following procedure. Suppose we start with an S_{i,k×n;(p,q)} board, 1 ≤ i ≤ k − j, then this board has k − i squares in the last column. Subsequently, choose j squares from this column, replace the chosen squares with dominoes. For each replacement,

since each square has weight p and each domino has weight q, we multiply s_{i,k×n;(p,q)} by (\frac{q}{p})^{j}. So now we obtain an S_{j,k×(n+1);(p,q)} board by filling the remaining (k−j) empty positions in

the n+1 column with squares. Thus, we need to multiply s_{i,k×n;(p,q)} (\frac{q}{p})^{j} by p^{k−j}. Therefore,

s_{j,k×(n+1);(p,q)} = ∑_{i=1}^{k−j} p^{k−2j}q^{j}\binom{k − i}{j}s_{i,k×n;(p,q)}

for 1 ≤ j ≤ k − 1.

In Figure 3, there is an example of Lemma 17.

Definition 18. For k ≥ 2, define matrices A_{k;(p,q)} = [a_{ji}]_{(k−1)×(k−1)} where a_{ji} = p^{k−2j}q^{j}\binom{k−i}{j}; B_{k} = [b_{1i}]_{1×(k−1)} such that b_{1i} = 1; C_{k;(0,1;p,q)} = [c_{j1}]_{(k−1)×1} where c_{j1} = p^{2(k−j)}q^{j}\binom{k}{j}, and I_{k} is the (k − 1) × (k − 1) identity matrix.

If k = 1, let A_{1;(p,q)} = B_{1} = C_{1;(0,1;p,q)} = 0, I_{1} = 1.

Lemma 19. For k ∈ ℕ^{+},

m_{k×n;(p,q)} = \begin{cases}q^{k} + B_{k}A_{k;(p,q)}^{0}C_{k;(0,1;p,q)}, & if n = 2; \\ B_{k}A_{k;(p,q)}^{n−2}C_{k;(0,1;p,q)}, & if n ≥ 3. \end{cases}

\begin{matrix}p \\ p \\ q \\ q \\ q \\ q \\ p \\ p \end{matrix}

Figure 3: How to transform S_{1,4×5;(p,q)} to S_{2,4×6;(p,q)}.

Proof. Employing Lemmas 13, 17, and 16, with k ∈ ℕ^{+} and n ≥ 3, we have,

m_{k×n;(p,q)} = ∑_{j=1}^{k−1} s_{j,k×n;(p,q)}
= B_{k}A_{k;(p,q)}^{n−2} [ s_{1,k×2;(p,q)} ; s_{2,k×2;(p,q)} ; ⋮ ; s_{k−1,k×2;(p,q)}]_{(k−1)×1}

= B_{k}A_{k;(p,q)}^{n−2} [p^{2(k−1)}q^{1}\binom{k}{1} ; p^{2(k−2)}q^{2}\binom{k}{2} ; ⋮ ; p^{2}q^{k−1}\binom{k}{k−1}]_{(k−1)×1}
= B_{k}A_{k;(p,q)}^{n−2}C_{k;(0,1;p,q)}.

For n = 2, m_{k×2;(p,q)} = q^{k} + ∑_{j=1}^{k−1} s_{j,k×2;(p,q)} = q^{k} + B_{k}A_{k;(p,q)}^{0}C_{k;(0,1;p,q)}. Table 2 contains s_{j,4×n;(2,−1)} for 2 ≤ n ≤ 7, with j = 1, 2, 3. We have that, s_{1,4×(n+1);(2,−1)} = (−12) · s_{1,4×n;(2,−1)} + (−8) · s_{2,4×n;(2,−1)} + (−4) · s_{3,4×n;(2,−1)}, s_{2,4×(n+1);(2,−1)} = 3 · s_{1,4×n;(2,−1)} + 1 · s_{2,4×n;(2,−1)} + 0 · s_{3,4×n;(2,−1)}, and s_{3,4×(n+1);(2,−1)} = (−\frac{1}{4}) · s_{1,4×n;(2,−1)} + 0 · s_{2,4×n;(2,−1)} + 0 · s_{3,4×n;(2,−1)}.

n  1  2  3  4  5  6  7
m_{4×n;(2,−1)} 16 −175 1760 −17456 172832 −1710896 16936160
s_{1,4×n;(2,−1)}  −256 2368 −23296 230464 −2281216 22581568
s_{2,4×n;(2,−1)}  96 −672 6432 −63456 627936 −6215712
s_{3,4×n;(2,−1)}  −16 64  −592  5824  −57616  570304

Table 2: s_{j,4×n;(2,−1)}, j = 1, 2, 3, for 2 ≤ n ≤ 7.

Example 20. From Lemma 19, and for n ≥ 3,

m_{4×n;(2,−1)} = s_{1,4×n;(2,−1)} + s_{2,4×n;(2,−1)} + s_{3,4×n;(2,−1)}
= [1 1 1] [\begin{matrix}−12 & −8 & −4 \\ 3 & 1 & 0 \\ −\frac{1}{4} & 0 & 0 \end{matrix}]^{n−2} [\begin{matrix}−256 \\ 96 \\ −16 \end{matrix}] .

Theorem 21. For k ∈ ℕ^{+},

𝒲_{k;(p,q)}(x) = \frac{x}{1 − p^{k}x − q^{k}x^{2} − x^{2}B_{k}(I_{k} − xA_{k;(p,q)})^{−1}C_{k;(0,1;p,q)}} .

Proof. For k ≥ 2, according to Lemmas 11, 16, and 19 we obtain,

e_{k;(p,q)} = ∑_{n=1}^{∞} m_{k×n;(p,q)}x^{n}

= p^{k}x + q^{k}x^{2} + ∑_{n=2}^{∞} B_{k}A_{k;(p,q)}^{n−2}C_{k;(0,1;p,q)}x^{n}

= p^{k}x + q^{k}x^{2} + x^{2} ∑_{n=0}^{∞} B_{k}A_{k;(p,q)}^{n}C_{k;(0,1;p,q)}x^{n}

= p^{k}x + q^{k}x^{2} + x^{2}B_{k} (∑_{n=0}^{∞}(xA_{k;(p,q)})^{n}) C_{k;(0,1;p,q)}
= p^{k}x + q^{k}x^{2} + x^{2}B_{k} (I_{k} − xA_{k;(p,q)})^{−1} C_{k;(0,1;p,q)}.

Thus,

𝒲_{k;(p,q)}(x) = \frac{x}{1 − e_{k;(p,q)}} = \frac{x}{1 − p^{k}x − q^{k}x^{2} − x^{2}B_{k}(I_{k} − xA_{k;(p,q)})^{−1}C_{k;(0,1;p,q)}} .

Since (B_{1}(I_{1} − xA_{1;(p,q)})^{−1}C_{1;(0,1;p,q)} = 0, the theorem is also true for k = 1. Example 22. Let k = 4, p = 2 and q = −1. Then

(I_{4} − xA_{4;(2,−1)})^{−1} = \frac{1}{1 + 11x + 11x^{2} + x^{3}} [\begin{matrix}1 − x & −8x & 4x(1 − x) \\ 3x & 1 + 12x − x^{2} & −12x^{2} \\ \frac{x(x−1)}{4} & 2x^{2} & 1 + 11x + 12x^{2} \end{matrix}] ,

B_{4}(I_{4} − xA_{4;(2,−1)})^{−1}C_{4;(0,1,2,−1)} = \frac{−16(2x^{2} + 11x + 11)}{1 + 11x + 11x^{2} + x^{3}},

therefore,

𝒲_{4;(2,−1)}(x) = \frac{x}{1 − 16x − x^{2} − x^{2} \frac{−16(2x^{2}+11x+11)}{1+11x+11x^{2}+x^{3}}} = \frac{x(1 + 11x + 11x^{2} + x^{3})}{(1 − x)^{5}}.

The polynomial 1 + 11x + 11x^{2} + x^{3} is the Eulerian polynomial A_{4}(x). Corollary 23. det(I_{k} − xA_{k;(2,−1)}) = A_{k}(x). Proof. By Theorem 21,

𝒲_{k;(p,q)}(x) = \frac{x}{1 − p^{k}x − q^{k}x^{2} − x^{2}B_{k}(I_{k} − xA_{k;(p,q)})^{−1}C_{k;(0,1;p,q)}}
= \frac{x}{1 − p^{k}x − q^{k}x^{2} − x^{2}B_{k} \frac{adj(I_{k}−xA_{k;(p,q)})}{det(I_{k}−xA_{k;(p,q)})}C_{k;(0,1;p,q)}}
= \frac{x det(I_{k} − xA_{k;(p,q)})}{(1 − p^{k}x − q^{k}x^{2}) det(I_{k} − xA_{k;(p,q)}) − x^{2}B_{k} adj(I_{k} − xA_{k;(p,q)})C_{k;(0,1;p,q)}} .

Therefore,

\frac{xA_{k}(x)}{(1 − x)^{k+1}} = ∑_{n=0}^{∞} n^{k}x^{n}
= 𝒲_{k;(2,−1)}(x)
= \frac{x det(I_{k} − xA_{k;(2,−1)})}{(1 − 2^{k}x − (−1)^{k}x^{2}) det(I_{k} − xA_{k;(2,−1)}) − x^{2}B_{k} adj(I_{k} − xA_{k;(2,−1)})C_{k;(0,1;2,−1)}} .

Since A_{k}(1) = k! ≠ 0, (1 − x) ∤ A_{k}(x) and deg (det(I_{k} − xA_{k;(2,−1)})) ≤ k − 1, then deg (det(I_{k} − xA_{k;(2,−1)})) = k − 1. Thus, det(I_{k} − xA_{k;(2,−1)}) = A_{k}(x).

Example 24. If k = 6,

det(I_{6} − xA_{6;(2,−1)}) = det [\begin{matrix}1 + 80x & 64x & 48x & 32x & 16x \\ −40x & 1 − 24x & −12x & −4x & 0 \\ 10x & 4x & 1 + x & 0 & 0 \\ \frac{−5x}{4} & \frac{−x}{4} & 0 & 1 & 0 \\ \frac{x}{16} & 0 & 0 & 0 & 1 \end{matrix}]

= 1 + 57x + 302x^{2} + 302x^{3} + 57x^{4} + x^{5}
= A_{6}(x).

Corollary 25. Let D_{k;(p,q)} = [d_{ji}]_{(k−1)×(k−1)} be the diagonal matrix with d_{jj} = p^{2j−k}q^{−j} and d_{ji} = 0 if j ≠ i. Then

det(D_{k;(p,q)} − xA_{k;(1,1)}) = det(I_{k} − xA_{k;(p,q)}).

Proof. Let λ_{ji} = 1 if j = i, otherwise λ_{ji} = 0. Then

det(I_{k} − xA_{k;(p,q)}) = det [λ_{ji} − p^{k−2j}q^{j}\binom{k − i}{j}x]_{(k−1)×(k−1)}
= det [p^{2j−k}q^{−j}λ_{ji} − \binom{k − i}{j}x]_{(k−1)×(k−1)}
= det [d_{ji} − \binom{k − i}{j}x]_{(k−1)×(k−1)}
= det(D_{k;(p,q)} − xA_{k;(1,1)}).

Remark 26. From Corollaries 23 and 25, we have

det(D_{k;(p,q)} − xA_{k;(1,1)}) = A_{k}(x).

Remark 27. From Corollary 23, Remark 26, and A_{k}(1) = k!, we have

det(I_{k} − A_{k;(2,−1)}) = det(D_{k;(2,−1)} − A_{k;(1,1)}) = k!.

References

[1] L. E. Dickson, History of the Theory of Numbers, Carnegie Institution, 1919.

[2] A. Dujella, A bijective proof of Riordan’s theorem on powers of Fibonacci numbers, Discrete Math. 199 (1999), 217–220.

[3] M. Katz and C. Stenson, Tiling a (2 × n)-board with squares and dominoes, J. Integer Sequences 12 (2009), Article 09.2.2.

[4] T. Mansour, A formula for the generating functions of powers of Horadam’s sequence, Australas. J. Combin. 30 (2004), 207–212.

[5] J. Riordan, Generating functions for powers of Fibonacci numbers, Duke Math. J. 29 (1962), 5–12.

[6] J. A. Sellers, Domino tilings and products of Fibonacci and Pell Numbers, J. Integer Sequences 5 (2002), Article 02.1.2.

[7] N. J. A. Sloane, The On-line Encyclopedia of Integer Sequences,

    http://www.oeis.org.

[8] P. Stănică, Generating functions, weighted and non-weighted sums for powers of secondorder recurrence sequences, Fibonacci Quart. 41 (2003), 321–333.

[9] Y. Zhang and G. Grossman, A combinatorial proof for the generating function of powers of the Fibonacci sequence, Fibonacci Quart. 55 (2017), 235–242.

2010 Mathematics Subject Classification: Primary 05A15. Keywords: generating function, second-order recurrence sequence, Pascal triangle, matrix, Eulerian polynomial.

(Concerned with sequences \underline{A000032}, \underline{A000045}, \underline{A000129}, \underline{A000290}, \underline{A000578}, \underline{A000583}, \underline{A000584}, \underline{A001014}, \underline{A001015}, \underline{A001016}, \underline{A001017}, \underline{A001045}, \underline{A001477}, \underline{A001582}, \underline{A007598}, \underline{A008292}, \underline{A008454}, \underline{A030186}, \underline{A056570}, \underline{A056571}, \underline{A056572}, \underline{A056573}, \underline{A056574}, \underline{A056585}, \underline{A056586}, \underline{A056587}, \underline{A079291}, \underline{A110272}, and \underline{A139818}.)

Received January 17 2017; revised versions received February 3 2017; November 1 2017; January 21 2018. Published in Journal of Integer Sequences, March 9 2018.

Return to Journal of Integer Sequences home page.