<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\usepackage[mathscr]{euscript}



\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\usepackage{subfigure}
\usepackage{indentfirst}

\usepackage{tikz}
\usetikzlibrary{patterns}
\DeclareMathOperator{\Deg}{deg}
\DeclareMathOperator{\Adj}{adj}

\newcommand{\R}{{\mathbb R}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\C}{{\mathbb C}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\Z}{{\mathbb Z}}

\makeatletter
\renewcommand{\@thesubfigure}{\hskip\subfiglabelskip}
\makeatother

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf A Combinatorial Proof for the Generating \\
\vskip .00in 
Function of Powers of a Second-Order \\
\vskip .13in
Recurrence Sequence}

\vskip 1cm
\large
Yifan Zhang and George Grossman\\
Department of Mathematics\\
Central Michigan University\\
Mount Pleasant, MI 48858\\
USA\\
\href{mailto:zhang5y@cmich.edu}{\tt zhang5y@cmich.edu}\\
\href{mailto:gross1gw@cmich.edu}{\tt gross1gw@cmich.edu}
\end{center}

\vskip .2 in

\begin{abstract}
In this paper, we derive a formula for the generating function of
powers of a second-order 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.
\end{abstract}

\section{Introduction}

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

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.$$ 

\begin{example}
The nonnegative integers are represented by $W_{n;(0,1;2,-1)}$.
\end{example}

Domino tiling methods have been used to find combinatorial identities and recurrence relations of certain sequences. Sellers~\cite{sellers2002domino} proved that the number of domino tilings of the graph $W_4\times P_{n-1}$ equals $F_nP_n$ (sequence \seqnum{A001582} in Sloane's \textit{On-Line Encyclopedia of Integer Sequences}~\cite{OEIS}), which is the product of the $n$-th Fibonacci number and the $n$-th Pell number. Katz and Stenson~\cite{katz2009tiling} considered the number of tilings of a $(2\times n)$-board \seqnum{A030186}.

Let $F_k(x)$ be the generating function for the
$k$-th powers of the Fibonacci numbers, defined by
$$F_k(x)=\sum_{n=0}^{\infty} F_n^kx^n, \text{  } k\in \N^+.$$
For $1\leq k \leq 10$, $F_k(x)$ can be found respectively from \seqnum{A000045}, \seqnum{A007598}, \seqnum{A056570}, \seqnum{A056571}, \seqnum{A056572}, \seqnum{A056573}, \seqnum{A056574}, \seqnum{A056585}, \seqnum{A056586}, and \seqnum{A056587} in Sloane's \textit{On-Line Encyclopedia of Integer Sequences}~\cite{OEIS} (OEIS).

In 1962, Riordan~\cite{riordan1965basic} gave the following recurrence relation,
$$(1-L_k(x)+(-1)^kx^2)F_k(x)=1+kx \sum_{j=1}^{\lfloor \frac{k}{2} \rfloor} (-1)^j \frac{A_{kj}}{j}F_{k-2j}\left((-1)^jx\right),$$
where $L_k$ is the $k$-th Lucas number \seqnum{A000032}. In 1999, Dujella~\cite{dujella1999bijective} showed the doubly-indexed sequence $A_{kj}$, has generating function given by,
$$(1-x-x^2)^{-j}=\sum_{k=2j}^{\infty} A_{kj}x^{k-2j}, \ j \geq 0.$$ 

In 2003, St\u anic\u a~\cite{stanica2000generating} 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 \in \Z, $$
such that $\delta=a^2+4b\ne0$. Let $\alpha=\frac{1}{2}(a+\sqrt{a^2+4b})$, $\beta=\frac{1}{2}(a-\sqrt{a^2+4b})$ and $A=\frac{U_1-U_0\beta}{\alpha-\beta}$, $B=\frac{U_1-U_0\alpha}{\alpha-\beta}$, $V_n=\alpha^n+\beta^n$ with initial conditions $V_0=2$, $V_1=a$, and let $U_k(x)=\sum_{i=0}^{\infty}U_i^k x^i$. 

If $k$ is odd, then
$$U_k(x)=\sum_{j=0}^{\frac{k-1}{2}} (-AB)^j \binom{k}{j}\frac{A^{k-2j}-B^{k-2j}+(-b)^j((B\alpha)^{k-2j}-(A\beta)^{k-2j})x}{1-(-b)^jV_{k-2j}x-b^kx^2}.$$

If $k$ is even, then
$$U_k(x)=\sum_{j=0}^{\frac{k}{2}-1} (-AB)^j \binom{k}{j}\frac{B^{k-2j}+A^{k-2j}-(-b)^j((B\alpha)^{k-2j}+(A\beta)^{k-2j})x}{1-(-b)^jV_{k-2j}x+b^kx^2}
+\binom{k}{\frac{k}{2}}\frac{(-AB)^{\frac{k}{2}}}{1-(-b)^{\frac{k}{2}}x}.$$

In 2004, Mansour~\cite{mansour2004formula} obtained a formula for the generating functions of powers of second-order recurrence sequence in terms of the determinants of certain matrices, given by
$$W_{n;(a,b;p,q)}(x)=\frac{\det(\delta_k)}{\det(\Delta_k)},$$
where 
\begin{align*}
\Delta_k &amp;=\begin{bmatrix} A_{1\times 1} &amp; C_{1\times (k-1)} \\ B_{(k-1)\times 1} &amp; D_{(k-1)\times (k-1)}\end{bmatrix}  \\[.1in]
\delta_k &amp;=\begin{bmatrix} E_{1\times 1} &amp; C_{1\times (k-1)} \\ F_{(k-1)\times 1} &amp; D_{(k-1)\times (k-1)}\end{bmatrix} \\[.1in]
A_{1\times 1} &amp;=\begin{bmatrix} 1-p^kx-q^kx^2\end{bmatrix} \\[.1in]
E_{1\times 1}&amp;=\begin{bmatrix} a^k+g_kx\end{bmatrix}, \\[.1in]
B_{(k-1)\times 1} &amp;=\begin{bmatrix} -p^{k-1}x &amp; -p^{k-2}x &amp; \cdots &amp; -p^1x \end{bmatrix}^T \\[.1in]
F_{(k-1)\times 1}&amp;=\begin{bmatrix} g_{k-1}x &amp; g_{k-2}x &amp; \cdots &amp; g_1x \end{bmatrix}^T, \\[.1in]
C_{1\times (k-1)} &amp;=\begin{bmatrix} -xp^{k-1}q^1\binom{k}{1} &amp; -xp^{k-2}q^2\binom{k}{2} &amp; \cdots &amp; -xp^{1}q^{k-1}\binom{k}{k-1} \end{bmatrix}, \\[.1in]
D_{(k-1)\times (k-1)} &amp;=\begin{bmatrix} 1-xp^{k-2}q^1\binom{k-1}{1} &amp; -xp^{k-3}q^2\binom{k-1}{2} &amp; \cdots &amp; -xq^{k-1}\binom{k-1}{k-1} \\ -xp^{k-3}q^1\binom{k-2}{1} &amp; 1-xp^{k-4}q^2\binom{k-2}{2} &amp; \cdots &amp; 0 \\ \vdots &amp; \vdots &amp; \ddots &amp; \vdots \\ -xq^1\binom{1}{1} &amp; 0 &amp; \cdots &amp; 1 \end{bmatrix},
\end{align*}
with $g_j=(b^j-a^jp^j)a^{k-j},$ $j=1$, $2$, $\ldots$, $k$.

In 2017, Zhang and Grossman~\cite{zhang2017Fibonacci} used a counting method to relate the number of tilings of a $(k\times 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 $$\sum_{n=0}^{\infty} n^kx^n=\frac{xA_k(x)}{(1-x)^{k+1}}.$$ 
The coefficients of Eulerian polynomials leads to the Eulerian numbers \seqnum{A008292}. The recurrence relation for nonnegative integers denoted $a_n$, $\ n \geq 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\ne0$, $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 \ref{cor:Ak(x)} and Remark \ref{rem:secondAk(x)}.

\section{Closed form for \texorpdfstring{$\mathscr{W}_{k;(0,1;p,q)}(x)$}{Lg}}


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

\begin{definition}
Let $\mathscr{W}_{k;(0,1;p,q)}(x)=\sum_{n=0}^{\infty} W_n^kx^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\in \R,$ $p\ne0$.
\end{definition}

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

\begin{definition}\label{FibonacciMinimalBoard}
For $k\geq 1$ and $n\geq 1$, let $F_{k\times n; (p,q)}$ denote the {\it Fibonacci} $(k \times n; (p,q))$ {\it checkerboard}, which is a {\it 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 $\mathcal{F}_{k\times n; (p,q)}$ be the set of all $F_{k\times n; (p,q)}$ boards. Define a function $V$: $\mathcal{F}_{k\times n; (p,q)} \rightarrow \R$ (value of $F_{k\times n; (p,q)}$) by $V(F_{k\times n; (p,q)})=p^sq^d$, where $d$ and $s$ denote the number of dominoes and squares respectively in this $F_{k\times n; (p,q)}$ board. Let us also redefine the function $V$:  $2^{\mathcal{F}_{k\times n; (p,q)}} \rightarrow \R$ by $V(A)=\sum_{a\in A}V(a)$. Let $w_{k\times n; (p,q)}=V(\mathcal{F}_{k\times n; (p,q)})$ be the sum of all the values of the different $F_{k\times n; (p,q)}$ boards.

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

We define $w_{k\times (-1); (p,q)}=0$ and $w_{k\times 0; (p,q)}=1$ for $k\in \N^+$.
\end{definition}

\begin{definition}
The {\it Fibonacci} $(k \times n; (p,q))$ {\it minimal checkerboard} called an $M_{k\times n; (p,q)}$ {\it board}, is an $F_{k\times n; (p,q)}$ board which cannot be vertically divided into two Fibonacci checkerboards. Let $\mathcal{M}_{k\times n; (p,q)}$ be the set of all $M_{k\times n; (p,q)}$ boards. Let $m_{k\times n; (p,q)}=V(\mathcal{M}_{k\times n; (p,q)})$ be the sum of all the values of the different $M_{k\times n; (p,q)}$ boards.
\end{definition}

Note that $\mathcal{M}_{k\times n; (p,q)}\subseteq \mathcal{F}_{k\times n; (p,q)}$.

\begin{example}
There are total of nine different $F_{2\times 3; (p,q)}$ boards shown in Figure \ref{9boards}. We find that 
$w_{2\times 3; (p,q)}=p^6+4p^4q+4p^2q^2$. There are two different $M_{2\times 3; (p,q)}$ boards and  $m_{2\times 3; (p,q)}=2p^2q^2$.
\end{example}

\begin{figure}[ht]
\begin{center}
\subfigure[$M_{2\times (1,1,1); (p,q)}$]  
{
\begin{tikzpicture}
\draw[step=1cm] (0,0) grid (3,2);
\end{tikzpicture}
}
\subfigure[$M_{2\times (1,2); (p,q)}$]
{
\begin{tikzpicture}
\draw[step=1cm] (4,1) grid (7,2);\draw (4,0) rectangle (5,1); \draw (5,0) rectangle (7,1);
\end{tikzpicture}
}
\subfigure[$M_{2\times (2,1); (p,q)}$]
{
\begin{tikzpicture}
\draw[step=1cm] (8,1) grid (11,2);\draw (8,0) rectangle (10,1); \draw (10,0) rectangle (11,1);
\end{tikzpicture}
}

\subfigure[$M_{2\times (1,2); (p,q)}$]
{
\begin{tikzpicture}
\draw[step=1cm] (0,-3) grid (3,-2);\draw (0,-2) rectangle (1,-1); \draw (1,-2) rectangle (3,-1);
\end{tikzpicture}
}
\subfigure[$M_{2\times (2,1); (p,q)}$]
{
\begin{tikzpicture}
\draw[step=1cm] (4,-3) grid (7,-2);\draw (4,-2) rectangle (6,-1); \draw (6,-2) rectangle (7,-1);
\end{tikzpicture}
}
\subfigure[$M_{2\times (1,2); (p,q)}$]
{
\begin{tikzpicture}
\draw[step=1cm] (8,-3) grid (9,-1);\draw (9,-2) rectangle (11,-1); \draw (9,-3) rectangle (11,-2);
\end{tikzpicture}
}

\subfigure[$S_{1,2\times 3; (p,q)}$]
{
\begin{tikzpicture}
\draw (0,-6) rectangle (2,-5); \draw (1,-5) rectangle (3,-4);\draw (0,-5) rectangle (1,-4); \draw (2,-6) rectangle (3,-5);
\end{tikzpicture}
}
\subfigure[$S_{1,2\times 3; (p,q)}$]
{
\begin{tikzpicture}
\draw (4,-6) rectangle (5,-5); \draw (5,-6) rectangle (7,-5);\draw (4,-5) rectangle (6,-4); \draw (6,-5) rectangle (7,-4);
\end{tikzpicture}
}
\subfigure[$M_{2\times (2,1); (p,q)}$]
{
\begin{tikzpicture}
\draw[step=1cm] (10,-6) grid (11,-4);\draw (8,-6) rectangle (10,-5); \draw (8,-5) rectangle (10,-4);
\end{tikzpicture}
}
\end{center}
\caption{Nine $F_{2\times 3; (p,q)}$ boards.}\label{9boards}
\end{figure}

\begin{lemma}\label{lem:wnpq}
For $n\geq 1$ and $k\geq 1$, $w_{1\times n;(p,q)}=W_{n+1;(p,q)}$ and $w_{k\times n;(p,q)}=W_{n+1;(p,q)}^k$.
\end{lemma}

\begin{proof} This lemma can be proven inductively.

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

If $w_{1\times n;(p,q)}=W_{n+1;(p,q)}$ and $w_{1\times (n+1);(p,q)}=W_{n+2;(p,q)}$ hold, then
$$w_{1\times (n+2);(p,q)}=pw_{1\times (n+1);(p,q)}+qw_{1\times n;(p,q)}=pW_{n+2;(p,q)}+qW_{n+1;(p,q)}=W_{n+3;(p,q)}.$$
Therefore $w_{1\times n;(p,q)}=W_{n+1;(p,q)}$ for $n\geq 1$.

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

The generating function for powers of Pell numbers (\seqnum{A000129}, \seqnum{A079291}, \seqnum{A110272}) is denoted $P_k(x)=\mathscr{W}_{k;(2,1)}(x)$; powers of Jacobsthal numbers (\seqnum{A001045}, \seqnum{A139818}), is denoted by $J_k(x)=\mathscr{W}_{k;(1,2)}(x)$; and powers of nonnegative integers (\seqnum{A001477}, \seqnum{A000290}, \seqnum{A000578}, \seqnum{A000583}, \seqnum{A000584}, \seqnum{A001014}, \seqnum{A001015}, \seqnum{A001016}, \seqnum{A001017}, and \seqnum{A008454}), is denoted  by $\mathscr{W}_{k;(2,-1)}(x)$.

In Table \ref{tab:m{4timesn}} we listed values of $m_{4\times n;(2,-1)}$ for $1\leq n \leq 7$. The smaller values were obtained by direct calculation, larger values were computed using Lemma \ref{lem:BACpq}. These values will be used to explain Example \ref{ex:W4} and Example \ref{ex:e4}.

\begin{table}[ht]
\begin{center}
\renewcommand{\arraystretch}{1.75}
    \begin{tabular} {|c|c|c|c|c|c|c|c|} \hline
	$n$                             &amp;  $1$  &amp;  $2$   &amp;  $3$     &amp;  $4$        &amp;  $5$      &amp;  $6$            &amp;  $7$                                     \\ \hline
     $m_{4\times n; (2,-1)}$ &amp; $16$ &amp; $-175$ &amp; $1760$ &amp; $-17456$ &amp; $172832$ &amp; $-1710896$ &amp; $16936160$       \\ \hline
	\end{tabular}
\caption{$m_{4\times n; (2,-1)}$ for $1\leq n \leq 7$.}\label{tab:m{4timesn}}
\end{center}
\end{table}

\begin{remark}\label{rem:uniquelyDivide}
Any non-minimal $F_{k\times n; (p,q)}$ board can be split uniquely into at most $n$ Fibonacci minimal boards. Specifically, there exist $j$, $1&lt; j \leq n$, and an ordered partition $n_1+n_2+\cdots+n_j=n$, such that the $F_{k\times n; (p,q)}$ board can be split into $M_{k\times n_1; (p,q)}$, $M_{k\times n_2; (p,q)}$, $\ldots$, $M_{k\times n_j; (p,q)}$ boards (from left to right).
\end{remark}

\begin{definition}
Let an $M_{k\times (n_1, n_2, \ldots, n_j); (p,q)}$ {\it board} be an $F_{k\times n; (p,q)}$ board with $n_1+n_2+\cdots+n_j=n$ that can be split into $M_{k\times n_1; (p,q)}$, $M_{k\times n_2; (p,q)}$, $\ldots$, $M_{k\times n_j; (p,q)}$ boards. Let $\mathcal{M}_{k\times (n_1, n_2, \ldots, n_j); (p,q)}$ be the set of all different $M_{k\times (n_1, n_2, \ldots, n_j); (p,q)}$ boards. Let 
$$m_{k\times (n_1, n_2, \ldots, n_j); (p,q)}=V(\mathcal{M}_{k\times (n_1, n_2, \ldots, n_j); (p,q)})$$
be the sum of all the values of the different $M_{k\times (n_1, n_2, \ldots, n_j); (p,q)}$ boards.
\end{definition}

The value of $m_{k\times (n_1, n_2, \ldots, n_j); (p,q)}$ is quantified in Lemma \ref{lem:Wnpq}. Note that there are two examples in Figure \ref{9boards}.

\begin{lemma}\label{lem:Wnpq}
For $k\geq 1$ and $n\geq 1$, $n_i\in \N^+$ for $i\in \{1,2, \ldots, j\}$ we have,
$$m_{k\times(n_1, n_2, \ldots, n_j); (p,q)}=\prod_{i=1}^{j} m_{k\times n_i; (p,q)},$$
and
$$W_{n+1; (p,q)}^k=\sum_{j=1}^{n} \sum_{n_1+n_2+\cdots+n_j=n} \prod_{i=1}^{j} m_{k\times n_i; (p,q)}.$$
\end{lemma}

\begin{proof}
Since an $M_{k\times(n_1, n_2, \ldots, n_j); (p,q)}$ board is the combination of $M_{k\times n_1; (p,q)}$, $M_{k\times n_2; (p,q)}$, $\ldots$, $M_{k\times n_j; (p,q)}$ boards, we have $m_{k\times(n_1, n_2, \ldots, n_j); (p,q)}=\prod_{i=1}^{j} m_{k\times n_i; (p,q)}$.

From Remark \ref{rem:uniquelyDivide}, each $F_{k\times n; (p,q)}$ board is either an $M_{k\times n; (p,q)}$ board or can be uniquely divided into $j$ minimal boards where $2\leq j \leq n$. Then the set 
$$\Big\{\mathcal{M}_{k\times n; (p,q)}, \bigcup_{n_1+n_2=n}\mathcal{M}_{k\times (n_1,n_2); (p,q)}, \ldots, \bigcup_{n_1+n_2+\cdots+n_n=n}\mathcal{M}_{k\times (n_1,n_2,\ldots,n_n); (p,q)}\Big\}$$ forms a partition of $\mathcal{F}_{k\times n; (p,q)}$. That is,
$$\mathcal{F}_{k\times n; (p,q)}=\mathcal{M}_{k\times n; (p,q)} \bigcup \left(\bigcup_{n_1+n_2=n}\mathcal{M}_{k\times (n_1,n_2); (p,q)}\right) \bigcup \cdots \bigcup \left(\bigcup_{n_1+n_2+\cdots+n_n=n}\mathcal{M}_{k\times (n_1,n_2,\ldots,n_n); (p,q)}\right).$$

Therefore, from Lemma \ref{lem:wnpq},
\begin{eqnarray*}
W_{n+1;(p,q)}^k&amp; = &amp;w_{k\times n;(p,q)}\\
&amp; = &amp;V(\mathcal{F}_{k\times n; (p,q)})\\
&amp; = &amp;V(\mathcal{M}_{k\times n; (p,q)})+V\left(\bigcup_{n_1+n_2=n}\mathcal{M}_{k\times (n_1,n_2); (p,q)}\right)+\cdots\\
&amp;  &amp;+V\left(\bigcup_{n_1+n_2+\cdots+n_n=n}\mathcal{M}_{k\times (n_1,n_2,\ldots,n_n); (p,q)}\right)\\
&amp; = &amp; m_{k\times n; (p,q)}+\sum_{n_1+n_2=n}m_{k\times (n_1,n_2); (p,q)}+\cdots+\sum_{n_1+n_2+\cdots+n_n=n}m_{k\times (n_1,n_2,\ldots,n_n); (p,q)}\\
&amp; = &amp; m_{k\times n; (p,q)}+\sum_{n_1+n_2=n}\prod_{i=1}^{2} m_{k\times n_i; (p,q)}+\cdots+\sum_{n_1+n_2+\cdots+n_n=n}\prod_{i=1}^{n} m_{k\times n_i; (p,q)}\\
&amp; = &amp;\sum_{j=1}^{n} \sum_{n_1+n_2+\cdots+n_j=n} \prod_{i=1}^{j} m_{k\times n_i; (p,q)}.
\end{eqnarray*}
\end{proof}

\begin{example}\label{ex:W4}
\begin{eqnarray*}
W_{4;(2,-1)}^4 &amp; = &amp;m_{4\times 3; (2,-1)}+m_{4\times (2,1); (2,-1)}+m_{4\times (1,2); (2,-1)}+ m_{4\times (1,1,1); (2,-1)}\\
&amp;=  &amp;1760+(-175)\cdot 16+16\cdot (-175)+16\cdot 16\cdot 16\\
&amp;=  &amp;256\\
&amp;= &amp;4^4.
\end{eqnarray*}
\end{example}

\begin{lemma}\label{lem:ek01pq}
For $k\in \N^+$, let $e_{k; (p,q)}=\sum_{n=1}^{\infty} m_{k\times n; (p,q)}x^n$. Then, $$\mathscr{W}_{k;(p,q)}(x)=\frac{x}{1-e_{k; (p,q)}}.$$
\end{lemma}

\begin{proof}
For $k,n\in \N^+$, the coefficient of $x^n$ in $e_{k; (p,q)}+e_{k; (p,q)}^2+\cdots+e_{k; (p,q)}^n+\cdots$ is
\begin{eqnarray*}
&amp;  &amp;m_{k\times n; (p,q)}+\sum_{\substack {n_1+n_2=n \\ n_i \in \N^+}} \prod_{i=1}^{2} m_{k\times n_i ; (p,q)}+\sum_{\substack {n_1+n_2+n_3=n \\ n_i \in \N^+}} \prod_{i=1}^{3} m_{k\times n_i ; (p,q)}+\cdots\\
&amp;  &amp;+\sum_{\substack {n_1+n_2+\cdots+n_n=n \\ n_i \in \N^+}} \prod_{i=1}^{n} m_{k\times n_i ; (p,q)}\\
&amp; = &amp; \sum_{j=1}^{n} \sum_{\substack {n_1+n_2+\cdots+n_j=n \\ n_i \in \N^+}} \prod_{i=1}^{j} m_{k\times n_i ; (p,q)}.
\end{eqnarray*}

Also, $e_{k; (p,q)}+e_{k; (p,q)}^2+\cdots+e_{k; (p,q)}^n+\cdots=\frac{1}{1-e_{k; (p,q)}}-1$. Therefore,
$$\sum_{n=1}^{\infty} \left(\left(\sum_{j=1}^{n} \sum_{\substack {n_1+n_2+\cdots+n_j=n \\ n_i \in \N^+}} \prod_{i=1}^{j} m_{k\times n_i ; (p,q)} \right)x^n\right)=\frac{1}{1-e_{k; (p,q)}}-1.$$

Employing Lemmas \ref{lem:wnpq} and \ref{lem:Wnpq}, we obtain,
\begin{eqnarray*}
\mathscr{W}_{k;(p,q)}(x) &amp;= &amp;\sum_{n=0}^{\infty} W_{n;(p,q)}^kx^n\\
&amp;= &amp;W_{0;(p,q)}^k+W_{1;(p,q)}^kx+\sum_{n=2}^{\infty} W_{n; (p,q)}^kx^n\\
&amp; =&amp; x+\sum_{n=1}^{\infty} W_{n+1; (p,q)}^kx^{n+1}\\
&amp; =&amp;x+x\sum_{n=1}^{\infty} W_{n+1;(p,q)}^kx^n\\
&amp; =&amp; x+x \sum_{n=1}^{\infty} \left(\left(\sum_{j=1}^{n} \sum_{\substack {n_1+n_2+\cdots+n_j=n \\ n_i \in \N^+}} \prod_{i=1}^{j} m_{k\times n_i ; (p,q)} \right)x^n\right)\\
&amp; =&amp; x+x\left(\frac{1}{1-e_{k; (p,q)}}-1\right)\\
&amp;= &amp;\frac{x}{1-e_{k; (p,q)}}.
\end{eqnarray*}\qedhere
\end{proof}

\begin{example}\label{ex:e4}
From Table \ref{tab:m{4timesn}}, we have $e_{4;(2,-1)}=\sum_{n=1}^{\infty} m_{4\times n; (2,-1)}x^n=16x-175x^2+1760x^3-\cdots$ and $\mathscr{W}_{4;(2,-1)}(x)=\frac{x}{1-e_{4;(2,-1)}}$.
\end{example}

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

\begin{lemma}\label{lem:matrixCH03}
Suppose $S_{1,n}$, $S_{2,n}$, $\ldots$, $S_{m,n}$ are real-valued sequences such that $S_{i,n+1}=\sum_{j=1}^{m} a_{i,j}S_{j,n}$ for $1\leq i \leq m$ and $n\geq 0$.

Let $[a_{i,j}]_{m\times m}=\begin{bmatrix} a_{1,1} &amp; a_{1,2} &amp; \cdots &amp; a_{1,m} \\ a_{2,1} &amp; a_{2,2} &amp; \cdots &amp; a_{2,m} \\ \vdots &amp; \vdots &amp; \ddots &amp; \vdots \\ a_{m,1} &amp; a_{m,2} &amp; \cdots &amp; a_{m,m} \end{bmatrix}_{m\times m}$,   $[S_{j,n}]_{m\times 1}=\begin{bmatrix} S_{1,n} \\ S_{2,n} \\ \vdots \\ S_{m,n}\end{bmatrix}_{m\times 1}$,
$B_{m+1}=\begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix}^T_{1\times m}$.
Then $\sum_{j=1}^{m} S_{j,n}=B_{m+1}[a_{i,j}]_{m\times m}^{n-l}[S_{j,l}]_{m\times 1}$.
\end{lemma}

\begin{proof}
Since
$$[a_{i,j}]_{m\times m}^{n-l}[S_{j,l}]_{m\times 1}=[a_{i,j}]_{m\times m}^{n-l-1}[a_{i,j}]_{m\times m}[S_{j,l}]_{m\times 1}=[a_{i,j}]_{m\times m}^{n-l-1}[S_{j,l+1}]_{m\times 1}=\cdots=[S_{j,n}]_{m\times 1},$$
then
$$\sum_{j=1}^{m} S_{j,n}=B_{m+1}[S_{j,n}]_{m\times 1}=B_{m+1}[a_{i,j}]_{m\times m}^{n-l}[S_{j,l}]_{m\times 1}.$$
\end{proof}

\begin{definition}
Let an $S_{j,k\times n; (p,q)}$ {\it board} $(j \in \{1,2,3, \ldots, k\}, n\geq 2)$ be an $M_{k\times n; (p,q)}$ board with $j$ dominoes in last two columns. Let $\mathcal{S}_{j,k\times n; (p,q)}$ be the set of all $S_{j,k\times n; (p,q)}$ boards. 
Let $s_{j,k\times n; (p,q)}=V(\mathcal{S}_{j,k\times n; (p,q)})$ be the sum of all the values of the different $S_{j,k\times n; (p,q)}$ boards.
\end{definition}

\begin{example}
In Figure \ref{examples}, the board on the left is an $S_{1,4\times 5; (p,q)}$ board and the board on the right is a combination of an $S_{1,4\times 3; (p,q)}$ board and an $S_{2,4\times 2; (p,q)}$ board.
\end{example}

\begin{figure}[ht]
\begin{center}
\subfigure[$M_{4\times 5; (p,q)}$, also $S_{1,4\times 5; (p,q)}$]
{
\begin{tikzpicture}
\draw (-2,-2) rectangle (-1,-1); \draw (-1,-2) rectangle (1,-1); \draw (1,-2) rectangle (2,-1); \draw (2,-2) rectangle (3,-1);
\draw (-2,-1) rectangle (-1,0); \draw (-1,-1) rectangle (0,0); \draw (0,-1) rectangle (1,0);\draw (1,-1) rectangle (3,0);
\draw (-2,0) rectangle (0,1);\draw (0,0) rectangle (2,1);\draw (2,0) rectangle (3,1);
\draw (-2,1) rectangle (0,2);\draw (0,1) rectangle (1,2);\draw (1,1) rectangle (2,2);\draw (2,1) rectangle (3,2);
\end{tikzpicture}
}
\subfigure[$M_{4\times (3,2); (p,q)}$]
{
\begin{tikzpicture}
\draw (6,-2) rectangle (7,-1); \draw (7,-2) rectangle (9,-1); \draw (9,-2) rectangle (10,-1); \draw (10,-2) rectangle (11,-1);
\draw (6,-1) rectangle (7,0); \draw (7,-1) rectangle (8,0); \draw (8,-1) rectangle (9,0);\draw (9,-1) rectangle (11,0);
\draw (6,0) rectangle (8,1);\draw (8,0) rectangle (9,1);\draw (9,0) rectangle (10,1);\draw (10,0) rectangle (11,1);
\draw (6,1) rectangle (8,2);\draw (8,1) rectangle (9,2);\draw (9,1) rectangle (11,2);
\end{tikzpicture}
}
\caption{Two different boards.}\label{examples}
\end{center}
\end{figure}


\begin{lemma}\label{lem:mpq}
For $k\in \N^+$, $s_{j,k\times 2; (p,q)}=p^{2(k-j)}q^j\binom{k}{j}$ for $1\leq j \leq k$ and 

\begin{displaymath}
m_{k\times n; (p,q)}=
\begin{cases}
p^k, &amp; \text{if $n=1$;}\\
q^k+\sum_{j=1}^{k-1} s_{j,k\times 2; (p,q)}, &amp; \text{if $n=2$;}\\
\sum_{j=1}^{k-1} s_{j,k\times n; (p,q)}, &amp; \text{if $n \geq 3$.}
\end{cases}
\end{displaymath}
\end{lemma}

\begin{proof}
For $n\geq 3$, $\mathcal{S}_{1,k\times n; (p,q)}$, $\mathcal{S}_{2,k\times n; (p,q)}$, $\ldots$, $\mathcal{S}_{k-1,k\times n; (p,q)}$ forms a partition of $\mathcal{M}_{k\times n; (p,q)}$.
Therefore,
$$m_{k\times n; (p,q)}=V(\mathcal{M}_{k\times n; (p,q)})=\sum_{j=1}^{k-1}V(\mathcal{S}_{j,k\times n; (p,q)})=\sum_{j=1}^{k-1}s_{j,k\times n; (p,q)}.$$

For $n=2$ and $j=k$, there is only one $S_{k,k\times 2; (p,q)}$ board and
$V(\mathcal{S}_{k,k\times 2; (p,q)})=q^k$. For $1\leq j \leq k-1$, there are $\binom{k}{j}$ different $S_{j,k\times 2; (p,q)}$ boards. Then $s_{j,k\times 2; (p,q)}=p^{2(k-j)}q^j\binom{k}{j}$. Therefore, $$m_{k\times 2; (p,q)}=q^k+\sum_{j=1}^{k-1} s_{j,k\times 2; (p,q)}=q^k+\sum_{j=1}^{k-1} p^{2(k-j)}q^j\binom{k}{j}.$$
\end{proof}

\begin{lemma}\label{lem:spq}
For $n\geq 2$ and $1\leq j \leq k-1$, 
$$s_{j,k\times (n+1); (p,q)}=\sum_{i=1}^{k-j} p^{k-2j}q^j\binom{k-i}{j}s_{i,k\times n; (p,q)}.$$
\end{lemma}

\begin{proof}
An $S_{j,k\times (n+1); (p,q)}$ board, $1\leq j \leq k-1$, can be obtained from an $S_{i,k\times n; (p,q)}$ board,  $1\leq i\leq k-j$, by the following procedure. Suppose we start with an $S_{i,k\times n; (p,q)}$ board,  $1\leq i\leq 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\times n; (p,q)}$ by $\left(\frac{q}{p}\right)^j$. 

So now we obtain an $S_{j,k\times (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\times n; (p,q)}\left(\frac{q}{p}\right)^j$ by $p^{k-j}$. Therefore, 
$$s_{j,k\times (n+1); (p,q)}=\sum_{i=1}^{k-j} p^{k-2j}q^j\binom{k-i}{j}s_{i,k\times n; (p,q)}$$ for $1\leq j \leq k-1$.
\end{proof}

In Figure \ref{transform01pq}, there is an example of Lemma \ref{lem:spq}.

\begin{figure}[ht]
\begin{center}
\begin{tikzpicture}
\draw (-2,-2) rectangle (-1,-1); \draw (-1,-2) rectangle (1,-1); \draw (1,-2) rectangle (2,-1); \draw (2,-2) rectangle (3,-1);
\draw (-2,-1) rectangle (-1,0); \draw (-1,-1) rectangle (0,0); \draw (0,-1) rectangle (1,0);\draw (1,-1) rectangle (3,0);
\draw (-2,0) rectangle (0,1);\draw (0,0) rectangle (2,1);\draw (2,0) rectangle (3,1);
\draw (-2,1) rectangle (0,2);\draw (0,1) rectangle (1,2);\draw (1,1) rectangle (2,2);\draw (2,1) rectangle (3,2);
\node at (2.5,1.5) {$p$};\node at (2.5,-1.5) {$p$};
\draw[-&gt;] (4.25,0) -- (5.75,0);

\draw (6,-2) rectangle (7,-1); \draw (7,-2) rectangle (9,-1); \draw (9,-2) rectangle (10,-1);
\draw (6,-1) rectangle (7,0); \draw (7,-1) rectangle (8,0); \draw (8,-1) rectangle (8,0);\draw (9,-1) rectangle (11,0);
\draw (6,0) rectangle (8,1);\draw (8,0) rectangle (10,1);\draw (10,0) rectangle (11,1);
\draw (6,1) rectangle (8,2);\draw (8,1) rectangle (9,2);\draw (9,1) rectangle (10,2);

\draw[-&gt;] (11.25,0) -- (12.75,0);

\draw (-2,-7) rectangle (-1,-6); \draw (-1,-7) rectangle (1,-6); \draw (1,-7) rectangle (2,-6); \draw (2,-7) rectangle (4,-6);
\draw (-2,-6) rectangle (-1,-5); \draw (-1,-6) rectangle (0,-5); \draw (0,-6) rectangle (1,-5);\draw (1,-6) rectangle (3,-5);
\draw (-2,-5) rectangle (0,-4);\draw (0,-5) rectangle (2,-4);\draw (2,-5) rectangle (3,-4);
\draw (-2,-4) rectangle (0,-3);\draw (0,-4) rectangle (1,-3);\draw (1,-4) rectangle (2,-3);\draw(2,-4) rectangle (4,-3);
\node at (3,-3.5) {$q$};\node at (3,-6.5) {$q$};
\draw[-&gt;] (4.25,-5) -- (5.75,-5);

\draw (6,-7) rectangle (7,-6); \draw (7,-7) rectangle (9,-6); \draw (9,-7) rectangle (10,-6); \draw (10,-7) rectangle (12,-6);
\draw (6,-6) rectangle (7,-5); \draw (7,-6) rectangle (8,-5); \draw (8,-6) rectangle (8,-5);\draw (9,-6) rectangle (11,-5);\draw (11,-6) rectangle (12,-5);
\draw (6,-5) rectangle (8,-4);\draw (8,-5) rectangle (10,-4);\draw (10,-5) rectangle (11,-4);\draw (11,-5) rectangle (12,-4);
\draw (6,-4) rectangle (8,-3);\draw (8,-4) rectangle (9,-3);\draw (9,-4) rectangle (10,-3);\draw (10,-4) rectangle (12,-3);
\node at (11,-3.5) {$q$};\node at (11,-6.5) {$q$};\node at (11.5,-4.5) {$p$};\node at (11.5,-5.5) {$p$};
\end{tikzpicture}
\caption{How to transform $S_{1,4\times 5; (p,q)}$ to $S_{2,4\times 6; (p,q)}$.}\label{transform01pq}
\end{center}
\end{figure}

\begin{definition}
For $k\geq 2$, define matrices $A_{k;(p,q)}=[a_{ji}]_{(k-1)\times (k-1)}$ where $a_{ji}=p^{k-2j}q^j\binom{k-i}{j}$; $B_{k}=[b_{1i}]_{1\times (k-1)}$ such that $b_{1i}=1$; $C_{k;(0,1;p,q)}=[c_{j1}]_{(k-1)\times 1}$ where $c_{j1}=p^{2(k-j)}q^j\binom{k}{j}$, and $I_k$ is the $(k-1)\times (k-1)$ identity matrix.

If $k=1$, let $A_{1;(p,q)}=B_1=C_{1;(0,1;p,q)}=0$, $I_1=1$.
\end{definition}

\begin{lemma}\label{lem:BACpq}
For $k\in \N^+$, 
\begin{displaymath}
m_{k\times n; (p,q)}=
\begin{cases}
q^k+B_{k}A_{k;(p,q)}^0C_{k;(0,1; p,q)}, &amp; \text{if $n=2$;}\\
B_{k}A_{k;(p,q)}^{n-2}C_{k;(0,1; p,q)}, &amp; \text{if $n \geq 3$.}
\end{cases}
\end{displaymath}
\end{lemma}

\begin{proof}
Employing Lemmas \ref{lem:matrixCH03},  \ref{lem:spq}, and \ref{lem:mpq}, with $k\in \N^+$ and $n \geq 3$, we have,
\begin{eqnarray*}
m_{k\times n; (p,q)} &amp; = &amp;\sum_{j=1}^{k-1} s_{j,k\times n; (p,q)}\\
&amp; = &amp;B_kA_{k;(p,q)}^{n-2}\begin{bmatrix} s_{1,k\times 2; (p,q)} \\ s_{2,k\times 2; (p,q)} \\ \vdots \\ s_{k-1,k\times 2; (p,q)}\end{bmatrix}_{(k-1)\times 1} \\
&amp; = &amp;B_kA_{k;(p,q)}^{n-2}\begin{bmatrix} p^{2(k-1)}q^1\binom{k}{1} \\ p^{2(k-2)}q^2\binom{k}{2} \\ \vdots \\ p^{2}q^{k-1}\binom{k}{k-1}\end{bmatrix}_{(k-1)\times 1}\\
&amp; = &amp;B_{k}A_{k;(p,q)}^{n-2}C_{k;(0,1; p,q)}.
\end{eqnarray*}

For $n=2$, $m_{k\times 2; (p,q)}=q^k+\sum_{j=1}^{k-1} s_{j,k\times 2; (p,q)}=q^k+B_{k}A_{k; (p,q)}^0C_{k; (0,1;p,q)}$.
\end{proof}

Table \ref{tab:sj4n} contains $s_{j,4\times n; (2,-1)}$ for $2 \leq n\leq 7$, with $j=1,2,3$. We have that,

$s_{1,4\times (n+1); (2,-1)}=(-12)\cdot s_{1,4\times n; (2,-1)}+(-8)\cdot s_{2,4\times n; (2,-1)}+(-4)\cdot s_{3,4\times n; (2,-1)}$,

$s_{2,4\times (n+1); (2,-1)}=3\cdot s_{1,4\times n; (2,-1)}+1\cdot s_{2,4\times n; (2,-1)}+0\cdot s_{3,4\times n; (2,-1)}$, and

$s_{3,4\times (n+1); (2,-1)}=(-\frac{1}{4})\cdot s_{1,4\times n; (2,-1)}+0\cdot s_{2,4\times n; (2,-1)}+0\cdot s_{3,4\times n; (2,-1)}$.

\begin{table}[ht]
\begin{center}
\renewcommand{\arraystretch}{1.75}
    \begin{tabular} {|c|c|c|c|c|c|c|c|} \hline
	$n$                             &amp;  $1$  &amp;  $2$   &amp;  $3$     &amp;  $4$        &amp;  $5$      &amp;  $6$            &amp;  $7$                 \\ \hline
     $m_{4\times n; (2,-1)}$ &amp; $16$ &amp; $-175$ &amp; $1760$ &amp; $-17456$ &amp; $172832$ &amp; $-1710896$ &amp; $16936160$       \\ \hline
    $s_{1,4\times n; (2,-1)}$          &amp;     &amp; $-256$ &amp; $2368$ &amp;  $-23296$ &amp; $230464$ &amp; $-2281216$ &amp; $22581568$       \\ \hline
    $s_{2,4\times n; (2,-1)}$          &amp;     &amp;  $96$   &amp; $-672$ &amp;   $6432$  &amp;  $-63456$ &amp;  $627936$   &amp; $-6215712$        \\ \hline
    $s_{3,4\times n; (2,-1)}$          &amp;     &amp;  $-16$  &amp;  $64$  &amp;    $-592$  &amp;  $5824$    &amp;    $-57616$ &amp;   $570304$         \\ \hline
	\end{tabular}
\end{center}
\caption{$s_{j,4\times n;(2,-1)}$, $j=1,2,3$, for $2\leq n \leq 7$.}\label{tab:sj4n}
\end{table}

\begin{example}
From Lemma \ref{lem:BACpq}, and for $n \geq 3$,
\begin{eqnarray*}
m_{4\times n; (2,-1)} &amp; = &amp;s_{1,4\times n; (2,-1)}+s_{2,4\times n; (2,-1)}+s_{3,4\times n; (2,-1)}\\
&amp; = &amp;
\begin{bmatrix} 1 &amp; 1 &amp; 1 \end{bmatrix}
\begin{bmatrix} -12 &amp; -8 &amp; -4 \\3 &amp; 1 &amp; 0 \\-\frac{1}{4} &amp;0 &amp; 0 \end{bmatrix}^{n-2}
\begin{bmatrix} -256 \\ 96 \\ -16\end{bmatrix}.
\end{eqnarray*}
\end{example}

\begin{theorem}\label{thm:main}
For $k\in \N^+$,
$$\mathscr{W}_{k;(p,q)}(x)=\frac{x}{1-p^kx-q^kx^2-x^2B_k(I_k-xA_{k; (p,q)})^{-1}C_{k; (0,1;p,q)}}.$$
\end{theorem}

\begin{proof}
For $k\geq 2$, according to Lemmas \ref{lem:ek01pq}, \ref{lem:mpq}, and \ref{lem:BACpq} we obtain,
\begin{eqnarray*}
e_{k;(p,q)} &amp; = &amp;\sum_{n=1}^{\infty} m_{k\times n; (p,q)}x^n \\
&amp; = &amp; p^kx+q^kx^2+\sum_{n=2}^{\infty} B_kA_{k; (p,q)}^{n-2}C_{k; (0,1;p,q)}x^n \\
&amp; = &amp; p^kx+q^kx^2+x^2\sum_{n=0}^{\infty} B_kA_{k; (p,q)}^nC_{k; (0,1;p,q)}x^n \\
&amp; = &amp; p^kx+q^kx^2+x^2 B_k\left(\sum_{n=0}^{\infty} (xA_{k; (p,q)})^n\right)C_{k; (0,1;p,q)} \\
&amp; = &amp; p^kx+q^kx^2+x^2 B_k\left(I_k-xA_{k; (p,q)}\right)^{-1}C_{k; (0,1;p,q)}.
\end{eqnarray*}

Thus, $$\mathscr{W}_{k;(p,q)}(x)=\frac{x}{1-e_{k;(p,q)}}=\frac{x}{1-p^kx-q^kx^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$.
\end{proof}

\begin{example}
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{bmatrix} 1-x &amp; -8x &amp; 4x(1-x) \\3x &amp; 1+12x-x^2 &amp; -12x^2 \\\frac{x(x-1)}{4} &amp; 2x^2 &amp; 1+11x+12x^2 \end{bmatrix},$$
$$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, $$\mathscr{W}_{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)$.
\end{example}

\begin{corollary}\label{cor:Ak(x)}
$\det(I_k-xA_{k;(2,-1)})=A_k(x)$.
\end{corollary}

\begin{proof}
By Theorem \ref{thm:main}, 
\begin{eqnarray*}
\mathscr{W}_{k;(p,q)}(x)&amp; = &amp;\frac{x}{1-p^kx-q^kx^2-x^2 B_k(I_k-xA_{k; (p,q)})^{-1}C_{k; (0,1;p,q)}}\\
&amp; = &amp;\frac{x}{1-p^kx-q^kx^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)}}\\
&amp; = &amp;\frac{x\det(I_k-xA_{k;(p,q)})}{(1-p^kx-q^kx^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)}}.
\end{eqnarray*}

Therefore,
\begin{eqnarray*}
\frac{xA_k(x)}{(1-x)^{k+1}}&amp; = &amp;\sum_{n=0}^{\infty} n^kx^n\\
&amp; = &amp;\mathscr{W}_{k;(2,-1)}(x)\\
&amp; = &amp;\frac{x\det(I_k-xA_{k;(2,-1)})}{(1-2^kx-(-1)^kx^2)\det(I_k-xA_{k;(2,-1)})-x^2B_k\Adj(I_k-xA_{k;(2,-1)})C_{k; (0,1;2,-1)}}.
\end{eqnarray*}

Since $A_k(1)=k!\ne 0$, $(1-x) \nmid A_k(x)$ and $\Deg\left(\det(I_k-xA_{k;(2,-1)})\right)\leq k-1$, then $\Deg\left(\det(I_k-xA_{k;(2,-1)})\right)= k-1$. Thus, $\det(I_k-xA_{k;(2,-1)})=A_k(x)$.
\end{proof}

\begin{example}
If $k=6$,
\begin{eqnarray*}
\det(I_6-xA_{6;(2,-1)}) &amp; = &amp;\det 
\begin{bmatrix} 1+80x &amp; 64x &amp; 48x &amp; 32x &amp; 16x\\-40x &amp; 1-24x &amp; -12x &amp; -4x &amp; 0\\10x &amp; 4x &amp; 1+x &amp; 0 &amp; 0\\\frac{-5x}{4} &amp; \frac{-x}{4} &amp; 0 &amp; 1 &amp; 0\\ \frac{x}{16} &amp; 0 &amp; 0 &amp; 0 &amp; 1 \end{bmatrix} \\
&amp; = &amp;1+57x+302x^2+302x^3+57x^4+x^5\\
&amp;= &amp;A_6(x).
\end{eqnarray*}
\end{example}

\begin{corollary}\label{cor:Dkpq}
Let $D_{k;(p,q)}=[d_{ji}]_{(k-1)\times (k-1)}$ be the diagonal matrix with $d_{jj}=p^{2j-k}q^{-j}$ and $d_{ji}=0$ if $j\ne i$. Then
$$\det(D_{k;(p,q)}-xA_{k;(1,1)})=\det(I_k-xA_{k;(p,q)}).$$
\end{corollary}

\begin{proof}
Let $\lambda_{ji}=1$ if $j=i$, otherwise $\lambda_{ji}=0$. Then 
\begin{eqnarray*}
\det(I_k-xA_{k;(p,q)}) &amp; = &amp;\det \left[\lambda_{ji}-p^{k-2j}q^j\binom{k-i}{j}x\right]_{(k-1)\times (k-1)} \\
&amp; = &amp;\det \left[p^{2j-k}q^{-j}\lambda_{ji}-\binom{k-i}{j}x\right]_{(k-1)\times (k-1)} \\
&amp;= &amp;\det \left[d_{ji}-\binom{k-i}{j}x\right]_{(k-1)\times (k-1)} \\
&amp;= &amp;\det(D_{k;(p,q)}-xA_{k;(1,1)}).
\end{eqnarray*}
\end{proof}

\begin{remark}\label{rem:secondAk(x)}
From Corollaries \ref{cor:Ak(x)} and \ref{cor:Dkpq}, we have 
$$\det(D_{k;(p,q)}-xA_{k;(1,1)})=A_k(x).$$
\end{remark}

\begin{remark}
From Corollary \ref{cor:Ak(x)},  Remark \ref{rem:secondAk(x)}, and $A_k(1)=k!$, we have
$$\det(I_k-A_{k;(2,-1)})=\det(D_{k;(2,-1)}-A_{k;(1,1)})=k!.$$
\end{remark}

\begin{thebibliography}{99}

\bibitem{dickson1954history}
L.~E.~Dickson, {\it History of the Theory of Numbers}, 
Carnegie Institution, 1919.

\bibitem{dujella1999bijective}
A.~Dujella, A bijective proof of Riordan's theorem on powers of Fibonacci numbers, {\it Discrete Math.} \textbf{199} (1999), 217--220.

\bibitem{katz2009tiling}
M.~Katz and C.~Stenson, Tiling a ($2\times n$)-board with squares and dominoes, {\it J. Integer Sequences} \textbf{12} (2009), \href{https://cs.uwaterloo.ca/journals/JIS/VOL12/Stenson/stenson8.html}{Article 09.2.2}.

\bibitem{mansour2004formula}
T.~Mansour, A formula for the generating functions of powers of Horadam's sequence, {\it Australas. J. Combin.} \textbf{30} (2004), 207--212.

\bibitem{riordan1965basic}
J.~Riordan, Generating functions for powers of Fibonacci numbers, {\it Duke Math. J.} \textbf{29} (1962), 5--12.

\bibitem{sellers2002domino}
J.~A.~Sellers, Domino tilings and products of Fibonacci and Pell
Numbers, {\it J. Integer Sequences} \textbf{5} (2002),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL5/Sellers/sellers4.html}{Article
02.1.2}.

\bibitem{OEIS}
N.~J.~A.~Sloane, \emph{The On-line Encyclopedia of Integer Sequences},\\ \url{http://www.oeis.org}.

\bibitem{stanica2000generating}
P.~St\u anic\u a, Generating functions, weighted and non-weighted sums for powers of second-order recurrence sequences, {\it Fibonacci Quart.} \textbf{41} (2003), 321--333.

\bibitem{zhang2017Fibonacci}
Y.~Zhang and G.~Grossman, A combinatorial proof for the generating function of powers of the Fibonacci sequence, {\it Fibonacci Quart.} \textbf{55} (2017), 235--242.

\end{thebibliography}
\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A15.

\noindent \emph{Keywords: }
generating function, second-order recurrence sequence, Pascal triangle, matrix, Eulerian polynomial.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  January 17 2017;
revised versions received  February 3 2017; November 1 2017;
January 21 2018.
Published in {\it Journal of Integer Sequences}, March 9 2018.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

</pre></body></html>