\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 &=\begin{bmatrix} A_{1\times 1} & C_{1\times (k-1)} \\ B_{(k-1)\times 1} & D_{(k-1)\times (k-1)}\end{bmatrix} \\[.1in] \delta_k &=\begin{bmatrix} E_{1\times 1} & C_{1\times (k-1)} \\ F_{(k-1)\times 1} & D_{(k-1)\times (k-1)}\end{bmatrix} \\[.1in] A_{1\times 1} &=\begin{bmatrix} 1-p^kx-q^kx^2\end{bmatrix} \\[.1in] E_{1\times 1}&=\begin{bmatrix} a^k+g_kx\end{bmatrix}, \\[.1in] B_{(k-1)\times 1} &=\begin{bmatrix} -p^{k-1}x & -p^{k-2}x & \cdots & -p^1x \end{bmatrix}^T \\[.1in] F_{(k-1)\times 1}&=\begin{bmatrix} g_{k-1}x & g_{k-2}x & \cdots & g_1x \end{bmatrix}^T, \\[.1in] C_{1\times (k-1)} &=\begin{bmatrix} -xp^{k-1}q^1\binom{k}{1} & -xp^{k-2}q^2\binom{k}{2} & \cdots & -xp^{1}q^{k-1}\binom{k}{k-1} \end{bmatrix}, \\[.1in] D_{(k-1)\times (k-1)} &=\begin{bmatrix} 1-xp^{k-2}q^1\binom{k-1}{1} & -xp^{k-3}q^2\binom{k-1}{2} & \cdots & -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} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ -xq^1\binom{1}{1} & 0 & \cdots & 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$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ \\ \hline $m_{4\times n; (2,-1)}$ & $16$ & $-175$ & $1760$ & $-17456$ & $172832$ & $-1710896$ & $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< 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& = &w_{k\times n;(p,q)}\\ & = &V(\mathcal{F}_{k\times n; (p,q)})\\ & = &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\\ & &+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)\\ & = & 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)}\\ & = & 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)}\\ & = &\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 & = &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)}\\ &= &1760+(-175)\cdot 16+16\cdot (-175)+16\cdot 16\cdot 16\\ &= &256\\ &= &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*} & &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\\ & &+\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)}\\ & = & \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) &= &\sum_{n=0}^{\infty} W_{n;(p,q)}^kx^n\\ &= &W_{0;(p,q)}^k+W_{1;(p,q)}^kx+\sum_{n=2}^{\infty} W_{n; (p,q)}^kx^n\\ & =& x+\sum_{n=1}^{\infty} W_{n+1; (p,q)}^kx^{n+1}\\ & =&x+x\sum_{n=1}^{\infty} W_{n+1;(p,q)}^kx^n\\ & =& 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)\\ & =& x+x\left(\frac{1}{1-e_{k; (p,q)}}-1\right)\\ &= &\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} & a_{1,2} & \cdots & a_{1,m} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \cdots & 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, & \text{if $n=1$;}\\ q^k+\sum_{j=1}^{k-1} s_{j,k\times 2; (p,q)}, & \text{if $n=2$;}\\ \sum_{j=1}^{k-1} s_{j,k\times n; (p,q)}, & \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[->] (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[->] (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[->] (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)}, & \text{if $n=2$;}\\ B_{k}A_{k;(p,q)}^{n-2}C_{k;(0,1; p,q)}, & \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)} & = &\sum_{j=1}^{k-1} s_{j,k\times n; (p,q)}\\ & = &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} \\ & = &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}\\ & = &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$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ \\ \hline $m_{4\times n; (2,-1)}$ & $16$ & $-175$ & $1760$ & $-17456$ & $172832$ & $-1710896$ & $16936160$ \\ \hline $s_{1,4\times n; (2,-1)}$ & & $-256$ & $2368$ & $-23296$ & $230464$ & $-2281216$ & $22581568$ \\ \hline $s_{2,4\times n; (2,-1)}$ & & $96$ & $-672$ & $6432$ & $-63456$ & $627936$ & $-6215712$ \\ \hline $s_{3,4\times n; (2,-1)}$ & & $-16$ & $64$ & $-592$ & $5824$ & $-57616$ & $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)} & = &s_{1,4\times n; (2,-1)}+s_{2,4\times n; (2,-1)}+s_{3,4\times n; (2,-1)}\\ & = & \begin{bmatrix} 1 & 1 & 1 \end{bmatrix} \begin{bmatrix} -12 & -8 & -4 \\3 & 1 & 0 \\-\frac{1}{4} &0 & 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)} & = &\sum_{n=1}^{\infty} m_{k\times n; (p,q)}x^n \\ & = & p^kx+q^kx^2+\sum_{n=2}^{\infty} B_kA_{k; (p,q)}^{n-2}C_{k; (0,1;p,q)}x^n \\ & = & p^kx+q^kx^2+x^2\sum_{n=0}^{\infty} B_kA_{k; (p,q)}^nC_{k; (0,1;p,q)}x^n \\ & = & 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)} \\ & = & 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 & -8x & 4x(1-x) \\3x & 1+12x-x^2 & -12x^2 \\\frac{x(x-1)}{4} & 2x^2 & 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)& = &\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)}}\\ & = &\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)}}\\ & = &\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}}& = &\sum_{n=0}^{\infty} n^kx^n\\ & = &\mathscr{W}_{k;(2,-1)}(x)\\ & = &\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)}) & = &\det \begin{bmatrix} 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{bmatrix} \\ & = &1+57x+302x^2+302x^3+57x^4+x^5\\ &= &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)}) & = &\det \left[\lambda_{ji}-p^{k-2j}q^j\binom{k-i}{j}x\right]_{(k-1)\times (k-1)} \\ & = &\det \left[p^{2j-k}q^{-j}\lambda_{ji}-\binom{k-i}{j}x\right]_{(k-1)\times (k-1)} \\ &= &\det \left[d_{ji}-\binom{k-i}{j}x\right]_{(k-1)\times (k-1)} \\ &= &\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}