\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} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \DeclareMathOperator{\ord}{ord} \DeclareMathOperator{\Nm}{Nm} \DeclareMathOperator{\Tr}{Sp} \DeclareMathOperator{\lcm}{lcm} \def\card#1{\#{#1}} \def\rad{\mathrm{rad}} \def\mand{\qquad \mbox{and} \qquad} \def\scr{\scriptstyle} \def\\{\cr} \def\({\left(} \def\){\right)} \def\[{\left[} \def\]{\right]} \def\<{\langle} \def\>{\rangle} \def\fl#1{\left\lfloor#1\right\rfloor} \def\rf#1{\left\lceil#1\right\rceil} \def\N{\mathbb{N}} \def\cA{\mathcal A} \def\cB{\mathcal B} \def\cC{\mathcal C} \def\cF{\mathcal F} \def\cD{\mathcal D} \def\cE{\mathcal E} \def\cH{\mathcal H} \def\cI{\mathcal I} \def\cJ{\mathcal J} \def\cL{\mathcal L} \def\cM{\mathcal M} \def\cN{\mathcal N} \def\cP{\mathcal P} \def\cQ{\mathcal Q} \def\cR{\mathcal R} \def\cS{\mathcal S} \def\cW{\mathcal W} \def\e{{\mathbf{\,e}}} \def\ep{{\mathbf{\,e}}_p} \def\eps{\varepsilon} \def\A{\mathcal A} \def\Z{\mathbb Z} \def\R{\mathbb R} \def\N{\mathbb N} \def\R{\mathbb{R}} \def\S{\mathcal{S}} \def\T{\mathcal{T}} \def\Zq{\mathbb{Z}_q} \def\Zqx{\mathbb{Z}_q^*} \def\Zd{\mathbb{Z}_d} \def\Zdx{\mathbb{Z}_d^*} \def\Zp{\mathbb{Z}_p} \def\Zpx{\mathbb{Z}_p^*} \def\M{\mathcal M} \def\E{\mathcal E} \def\F{\mathbb{F}} \def\Fp{\mathbb{F}_p} \def\Z{\mathbb{Z}} \def\K{\mathbb{K}} \def\Q{\mathbb{Q}} \def\Il{\cI_\ell} \newcommand{\comm}[1]{\marginpar {\fbox{#1}}} \def\xxx{\vskip5pt\hrule\vskip5pt} \def\yyy{\vskip5pt\hrule\vskip2pt\hrule\vskip5pt} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Generating Matrices for Weighted Sums \vskip .1in of Second Order Linear Recurrences } \vskip 1cm \large Emrah Kili\c{c} \\ TOBB Economics and Technology University\\ Mathematics Department\\ 06560 Sogutozu, Ankara \\ Turkey\\ \href{mailto:ekilic@etu.edu.tr}{\tt ekilic@etu.edu.tr} \\ \ Pantelimon St\u anic\u a\\ Naval Postgraduate School\\ Applied Mathematics Department\\ Monterey, CA 93943 \\ USA \\ \href{mailto:pstanica@nps.edu}{\tt pstanica@nps.edu} \\ \end{center} \vskip .2 in \begin{abstract} In this paper, we give fourth order recurrences and generating matrices for the weighted sums of second order recurrences. We derive by matrix methods some new explicit formulas and combinatorial representations, and some relationships between the permanents of certain superdiagonal matrices and these sums. \end{abstract} \newtheorem{lem}{Lemma} \newtheorem{lemma}[lem]{Lemma} \newtheorem{prop}{Proposition} \newtheorem{proposition}[prop]{Proposition} \newtheorem{thm}{Theorem} \newtheorem{theorem}[thm]{Theorem} \newtheorem{cor}{Corollary} \newtheorem{corollary}[cor]{Corollary} \newtheorem{conj}{Conjecture} \newtheorem{prob}{Problem} \newtheorem{problem}[prob]{Problem} \newtheorem{ques}{Question} \newtheorem{question}[ques]{Question} \section{Introduction} Let $A$ be an integer such that $A^{2}+4\not=0.$ Define the second order linear recurrence $\left\{ U_{n}\right\} $ as follows: for $n>0$, let \begin{equation*} U_{n}=AU_{n-1}+U_{n-2} \end{equation*}% where $U_{0}=0$ and $U_{1}=1.$ We also let $V_n$ be the companion sequence satisfying the same recurrence with initial conditions $V_0=2,V_1=A$. For example, when $A=1,$ then $U_{n}=F_{n}$ (the $n$th Fibonacci number). Also, when $A=2,$ then $U_{n}=P_{n}$ (the $n$th Pell number). Many authors have studied various sums of certain products of terms of second order recurrences. Recently, the first author gave a new generating matrix, recurrence relation and some identities for squares and double products of terms of a second order linear recurrence via its generating matrix \cite{Kilic}. Matrix methods are very useful tools in solving problems stemming from number theory. Further, some authors have studied weighted sums of terms of certain recurrences. For example, the following sums can be found in \cite{Koshy}: \begin{eqnarray*} &&\sum\limits_{i=1}^{n}iF_{i}=nF_{n+2}-F_{n+3}+2 \\ &&\sum\limits_{i=1}^{n}\left( n-i+1\right) F_{i}=F_{n+4}-n-3 \end{eqnarray*}% In this paper, we consider the following weighted sum of terms of $\left\{ U_{n}\right\} ,$ for $n,t>0$% \begin{equation} B_{n,t}=\sum\limits_{i=1}^{n}\left( n-i\right) U_{ti} \label{1} \end{equation}% The first few initial terms of $\left\{ B_{n,1}\right\} $ are \begin{equation*} 0,1,\allowbreak A+2,\allowbreak A^{2}+2A+4,A^{3}+2A^{2}+5A+6,\allowbreak A^{4}+2A^{3}+6A^{2}+8A+9,.... \end{equation*}% For $A=1,$ the Fibonacci case, the first few terms of $\left\{ B_{n,1}\right\} $ are% \begin{equation*} \allowbreak 1,\allowbreak 3,\allowbreak 7,\allowbreak 14,\allowbreak 26,\allowbreak 46,\allowbreak 79,\allowbreak 133,\allowbreak 221, \ldots, \end{equation*} which is Sloane's sequence \seqnum{A001924}. We derive two fourth order recurrence relations and two generating matrices for the weighted sums sequence $\left\{ B_{n,t}\right\}.$ We obtain some new\ explicit formulas and combinatorial representations for the weighted sums by matrix methods, involving certain superdiagonal determinants and the weighted sums. Further the generating functions for the sum sequences $% \left\{ B_{n,t}\right\} $ for both even and odd integers $n$ are obtained. \section{Recurrence relations for the weighted sums} In this section, we derive two fourth order recurrence relations for the sequence $\left\{ B_{n,t}\right\} $ for both the even and odd subscripted terms. \begin{lemma} \label{lem1}For even integers $t=2r$, $r>0,$ the sequence $\left\{ B_{n,t}\right\} $ satisfies the recurrence \begin{equation} \label{eq1lem1} B_{n,t}=\left( V_{t}+2\right) B_{n-1,t}-2\left( V_{t}+1\right) B_{n-2,t}+\left( V_{t}+2\right) B_{n-3,t}-B_{n-4,t},\ n>3, \end{equation}% where $B_{0,t}=0,B_{1,t}=0,B_{2,t}=U_{t},B_{3,t}=\left( 2U_{t}+U_{2t}\right) /U_{t}.$ Furthermore, for odd integers $t=2r+1$, $r\geq 0,$ the sequence $% \left\{ B_{n,t}\right\} $ satisfies the recurrence \begin{equation} \label{eq2lem1} B_{n,t}=\left( V_{t}+2\right) B_{n-1,t}-2V_{t}B_{n-2,t}+\left( V_{t}-2\right) B_{n-3,t}+B_{n-4,t},\ n>3, \end{equation}% where $B_{0,t}=0,B_{1,t}=0,B_{2,t}=U_{t},B_{3,t}=\left( 2U_{t}+U_{2t}\right) /U_{t}.$ \end{lemma} \begin{proof} First, observe that $\displaystyle B_{k,t}-B_{k-1,t}=\sum_{i=1}^{k-1} U_{ti}$% . Next, we write the right-hand side of equation \eqref{eq1lem1} in the following way \begin{eqnarray*} &&(V_t+2) B_{n-1,t}-2(V_t+1) B_{n-2,t}+ (V_t+2) B_{n-3,t}-B_{n-4,t} \\ &=&V_t( B_{n-1,t}-2 B_{n-2,t}+B_{n-3,t}) +2 ( B_{n-1,t}-B_{n-2,t}+B_{n-3,t}-B_{n-4,t})+B_{n-4,t} \\ &=&V_t( \sum_{i=1}^{n-2}U_{ti}-\sum_{i=1}^{n-3}U_{ti} ) +2\left( \sum_{i=1}^{n-2}U_{ti}+ \sum_{i=1}^{n-4}U_{ti}\right) + B_{n-4,t} \\ &=& V_t U_{t(n-2)} +4 \sum_{i=1}^{n-4}U_{ti}+2 U_{t(n-3)}+2 U_{t(n-2)} + \sum_{i=1}^{n-4}(n-4-i)U_{ti} \\ &=& V_t U_{t(n-2)}+2 U_{t(n-3)}+2 U_{t(n-2)}+\sum_{i=1}^{n-4}(n-i)U_{ti} \\ &=& V_t U_{t(n-2)}+2 U_{t(n-3)}+2 U_{t(n-2)}+B_{n,t}-3 U_{t(n-3)}-2 U_{t(n-2)} -U_{t(n-1)} \\ &=& V_t U_{t(n-2)}- U_{t(n-3)}- U_{t(n-1)}+B_{n,t} =B_{n,t}, \end{eqnarray*}% since $V_t U_{t(n-2)}= U_{t(n-1)}+(-1)^t U_{t(n-3)}=U_{t(n-1)}+ U_{t(n-3)}$, when $t$ is even, and the proof of the first claim is complete. The second claim for odd integers $t$ follows similarly \begin{eqnarray*} &&(V_t+2) B_{n-1,t}-2V_t B_{n-2,t}+ (V_t-2) B_{n-3,t}+B_{n-4,t} \\ &=&V_t( B_{n-1,t}-2 B_{n-2,t}+B_{n-3,t}) +2(B_{n-1,t}-B_{n-3,t})+B_{n-4,t} \\ &=& V_t U_{t(n-2)}+4 \sum_{i=1}^{n-4}U_{ti}+2 U_{t(n-2)}+\sum_{i=1}^{n-4}(n-4-i)U_{ti} \\ &=& V_t U_{t(n-2)}+2 U_{t(n-3)}+2 U_{t(n-2)}+\sum_{i=1}^{n-4}(n-i)U_{ti} \\ &=& V_t U_{t(n-2)}+ U_{t(n-3)}- U_{t(n-1)}+B_{n,t} =B_{n,t}, \end{eqnarray*} where we used that $V_t U_{t(n-2)}= U_{t(n-1)}+(-1)^t U_{t(n-3)}=U_{t(n-1)}- U_{t(n-3)}$, if $t$ odd. \end{proof} The next corollary can be derived from a straightforward application of the previous lemma (or it can also be proved directly). \begin{cor} For even $t=2r$, $r>0,$% \begin{equation*} \sum\limits_{n=0}^{\infty }B_{n,t}x^{n}=\frac{U_{t}x^{2}-4U_{t}\left( V_{t}+1\right) x^{4}}{1-\left( V_{t}+2\right) x+2\left( V_{t}+1\right) x^{2}-\left( V_{t}+2\right) x^{3}+x^{4}}. \end{equation*} For odd integers $t=2r+1$, $r\geq 0,$ \begin{equation*} \sum\limits_{n=0}^{\infty }B_{n,t}x^{n}=\frac{U_{t}x^{2}}{1-\left( V_{t}+2\right) x+2V_{t}x^{2}-\left( V_{t}-2\right) x^{3}-x^{4}}. \end{equation*} \end{cor} In \cite{Chen}, the authors obtain an explicit formula for the $n$th power of general companion matrix. Let the $k\times k$ companion matrix be \begin{equation} A_{k}=\left[ \begin{array}{cccccc} c_{1} & c_{2} & c_{3} & \ldots & c_{k-1} & c_{k} \\ 1 & 0 & 0 & \ldots & 0 & 0 \\ 0 & 1 & 0 & \ldots & 0 & 0 \\ 0 & 0 & 1 & \ldots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \ldots & 1 & 0% \end{array}% \right] . \label{11} \end{equation} \begin{theorem}[\protect\cite{Chen}] \label{Thm1}The $\left( i,j\right) $ entry \ $a_{ij}^{\left( n\right) }\left( c_{1},\ldots ,c_{k}\right) $ in the matrix $A_{k}^{n}\left( c_{1}, \ldots ,c_{k}\right) $ is given by the following formula:% \begin{equation} a_{ij}^{\left( n\right) }\left( c_{1},c_{2},\ldots ,c_{k}\right) =\sum\limits_{\left( t_{1},t_{2},\ldots t_{k}\right) }\frac{% t_{j}+t_{j+1}+\cdots +t_{k}}{t_{1}+t_{2}+\cdots +t_{k}}\times \binom{% t_{1}+t_{2}+\cdots +t_{k}}{t_{1},t_{2},\ldots ,t_{k}}c_{1}^{t_{1}}\ldots c_{k}^{t_{k}} \label{12} \end{equation}% where the summation is over nonnegative integers satisfying $% t_{1}+2t_{2}+\cdots +kt_{k}=n-i+j,$ and the coefficients in \eqref{12} are defined to be $1$ if $n=i-j.$ \end{theorem} Applying the previous theorem in our case, we get the following consequence. \begin{corollary} For $r>0,$% \begin{eqnarray*} &&\sum\limits_{i=1}^{n}\left( n-i\right) U_{2ir} \\ &=&\sum\limits_{\left( n_{1},n_{2},n_{3},n_{4}\right) }\binom{% n_{1}+n_{2}+n_{3}+n_{4}}{n_{1},n_{2},n_{3},n_{4}}\left( -1\right) ^{n_{2}+n_{4}}\left( V_{2r}+2\right) ^{n_{1}+n_{3}}\left( 2V_{2r}+2\right) ^{n_{2}}, \end{eqnarray*}% and, for $r\geq 0$, \begin{eqnarray*} &&\sum\limits_{i=1}^{n}\left( n-i\right) U_{i\left( 2r+1\right) } \\ &=&\sum\limits_{\left( n_{1},n_{2},n_{3},n_{4}\right) }\binom{% n_{1}+n_{2}+n_{3}+n_{4}}{n_{1},n_{2},n_{3},n_{4}}\left( V_{2r+1}+2\right) ^{n_{1}}\left( -2V_{2r+1}\right) ^{n_{2}}\left( V_{2r+1}-2\right) ^{n_{3}}, \end{eqnarray*} where the summations are over nonnegative integers satisfying $% n_{1}+2n_{2}+3n_{3}+4n_{4}=n-2.$ \end{corollary} \begin{proof} In Theorem~\ref{Thm1}, if $i=3,~j=1$,$~c_{1}=c_{3}=V_{2r}+2$, $% c_{2}=-2\left( V_{2r}+1\right) $ and $c_{4}=-1,$ then the proof of the first claim follows immediately from \eqref{12}. Similarly, the proof of the second claim follows immediately from \eqref{12} if we take $i=3,~j=1$,$~c_{1}=c_{3}=V_{2r}+2$, $c_{2}=-2\left( V_{2r}+1\right) $ and $c_{4}=-1$ in Theorem~\ref{Thm1}. \end{proof} Next we derive generating matrices for the even and odd subscripted weighted sums. For this purpose, we define two auxiliary sequences via the sequence $% \left\{ B_{n,t}\right\} $. First we consider the even subscripted weighted sums. Define two sequences as shown: for $n>3$ and even $t$ such that $t=2r,$~$r>0 $ \begin{equation} Q_{n,t}=\left( V_{t}+2\right) B_{n-1,t}-B_{n-2,t} \label{rec2} \end{equation}% and for $n>2$ \begin{equation} H_{n,t}=-2\left( V_{t}+1\right) B_{n,t}+Q_{n,t} \label{rec3} \end{equation}% where $Q_{3,t}=V_{t}+2,Q_{2,t}=Q_{1,t}=0,Q_{0,t}=1$ and $H_{2,t}=-2\left( V_{t}+1\right) ,H_{1,t}=0,H_{0,t}=1,H_{-1,t}=0,$ respectively. From Lemma \ref{lem1}, we write the vector recurrence: for even $t$ such that $t=2r,$~$r>0$ \begin{equation*} \left[ \begin{array}{c} B_{n+1,t} \\ B_{n,t} \\ B_{n-1,t} \\ B_{n-2,t}% \end{array}% \right] =\left[ \begin{array}{cccc} V_{t}+2 & -2\left( V_{t}+1\right) & V_{t}+2 & -1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0% \end{array}% \right] \left[ \begin{array}{c} B_{n,t} \\ B_{n-1,t} \\ B_{n-2,t} \\ B_{n-3,t}% \end{array}% \right] . \end{equation*}% By \eqref{rec2} and \eqref{rec3}, we generalize the above vector recurrence relation to the matrix recurrence relation:% \begin{equation} \label{E-1} T_{n+1,t}=D_{t}T_{n-1,t}=\cdots=D_t^{n-1} T_{1,t}=D_t^n \end{equation}% where% \begin{equation} \label{Tnt} T_{n,t}=\frac{1}{B_{2,t}}\left[ \begin{array}{cccc} B_{n+2,t} & H_{n+1,t} & Q_{n+2,t} & -B_{n+1,t} \\ B_{n+1,t} & H_{n,t} & Q_{n+1,t} & -B_{n,t} \\ B_{n,t} & H_{n-1,t} & Q_{n,t} & -B_{n-1,t} \\ B_{n-1,t} & H_{n-2,t} & Q_{n-1,t} & -B_{n-2,t}% \end{array}% \right] \end{equation}% and% \begin{equation*} \text{ }D_{t}=\left[ \begin{array}{cccc} V_{2r}+2 & -2\left( V_{2r}+1\right) & V_{2r}+2 & -1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0% \end{array}% \right](=T_{1,t}). \end{equation*}% Since $T_{n,t}=T_{n-1,t}T_{1,t}=T_{1,t}T_{n-1,t},$ we have the following result. \begin{corollary} \label{cor1} For $n>3$ and $r>0,$ the sequences $\left\{ H_{n,2r}\right\} $ and $\left\{ Q_{n,2r}\right\} $ satisfy the following recurrence \begin{equation*} x_{n}=\left( V_{2r}+2\right) x_{n-1}-2\left( V_{2r}+1\right) x_{n-2}+\left( V_{2r}+2\right) x_{n-3}-x_{n-4}, \end{equation*}% where $x_{n}$ is either $Q_{n,2r}$ or $H_{n-1,2r}.$ \end{corollary} By the Binet formula for $\left\{ U_{n}\right\} $, it is easy to show that $% U_{kn}=V_{k}U_{k\left( n-1\right) }+\left( -1\right) ^{k+1}U_{k\left( n-2\right) }$, for integers $n>1,k>0$. Without effort we obtain \begin{corollary} \label{cor2} For $n,k>0,$ $U_{k}\mid U_{kn}.$ \end{corollary} Perhaps it is worth mentioning that $B_{2,t}=U_{t}$ divides $B_{n,t}$ for all $n>1.$ Similar to the case of the even subscripted sums, we derive similar results for the odd subscripted sums. For odd $t=2r+1$, we define the sequences $\left\{ Q_{n,t}\right\} $ and $\left\{ H_{n,t}\right\} $, as follows \begin{equation} Q_{n,t}=\left( V_{t}+2\right) B_{n-1,t}+B_{n-2,t},\ n>3, \label{rec4} \end{equation}% and \begin{equation} H_{n,t}=-2V_{t}B_{n,t}+Q_{n,t},\ n>2, \label{rec5} \end{equation}% where $Q_{3,t}=V_{t}+2,Q_{2,t}=Q_{1,t}=0,Q_{0,t}=1$ and $% H_{2,t}=-2V_{t},H_{1,t}=0,H_{0,t}=1,H_{-1,t}=0,$ respectively. Combining Lemma~\ref{lem1}, \eqref{rec4} and \eqref{rec5}, for odd $t=2r+1,$ we write% \begin{equation} T_{n,t}=D_{t}^{n} \label{E-2} \end{equation}% where $T_{n,t}$ is as in \eqref{Tnt} and% \begin{equation*} D_{t}=\left[ \begin{array}{cccc} V_{2r+1}+2 & -2V_{2r+1} & V_{2r+1}-2 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0% \end{array}% \right] . \end{equation*} Since $T_{n,t}=T_{n-1,t}T_{1,t}=T_{1,t}T_{n-1,t},$ we have the following result. \begin{corollary} \label{cor3}For $n>3$ and $r\geq 0,$ the sequences $\left\{ H_{n,2r+1}\right\} $ and $\left\{ Q_{n,2r+1}\right\} $ satisfy the recurrence \begin{equation*} x_{n}=\left( V_{2r+1}+2\right) x_{n-1}-2V_{2r+1}x_{n-2}+\left( V_{2r+1}-2\right) x_{n-3}+x_{n-4} \end{equation*}% where $x_{n}$ is either $Q_{n,2r+1}$ or $H_{n-1,2r+1}.$ \end{corollary} Since the matrix $D_{t}$ does not have linear independent eigenvectors for all $t$, we cannot diagonalize the matrix. In the next section, we are able to get explicit formulas for the even and odd subscripted weighted sums by using alternative linear algebra methods instead of diagonalization. \section{Explicit Formulas for the Weighted Sums $B_{n,t}$ by Matrix Methods} In this section, we derive some new explicit formulas for the weighted sums $% B_{n,t}$ for both even and odd $n$. In order to obtain explicit formulas, we use triangulization instead of diagonalization. After computing the $n$th power of a triangular matrix, we can show that our generating matrices are similar to certain triangular matrices via an invertible Vandermonde-like matrix. Now, we reconsider the matrix $D_{t}$ for both odd and even $t$. After simple computations, the characteristic polynomial of the matrix $D_{t}$ can be written as \begin{equation*} C\left( x\right) =\left( x^{2}-V_{t}x+1\right) \left( x-1\right) ^{2} \end{equation*}% whose roots are $\alpha ^{t},\beta ^{t}$ and $1.$ The matrix $D_{t}$ has linear dependent eigenvectors for both cases of $t$. So we cannot diagonalize the matrix $D_{t}.$ For later use, we define a triangular matrix and then we compute its $n$th power. Let $t,r,s$ and $m$ be arbitrary real numbers. Define two $\left( 4\times 4\right) $ upper triangular matrices $H\left( r_{1},r_{2},r_{3},r_{4}\right) $ and $W_{n}$ by \begin{equation*} H\left( r_{1},r_{2},r_{3},r_{4}\right) =\left[ \begin{array}{cccc} r_{1} & 0 & 0 & 0 \\ 1 & r_{2} & 0 & 0 \\ 1 & 0 & r_{3} & 0 \\ 1 & 0 & 0 & r_{4}% \end{array}% \right] \end{equation*} and \begin{equation*} W_{n}=\left[ \begin{array}{cccc} r_{1}^{n} & 0 & 0 & 0 \\ f_{n}\left( r_{1},r_{2}\right) & r_{2}^{n} & 0 & 0 \\ f_{n}\left( r_{1},r_{3}\right) & 0 & r_{3}^{n} & 0 \\ f_{n}\left( r_{1},r_{4}\right) & 0 & 0 & r_{4}^{n}% \end{array}% \right],\ n>0, \end{equation*}% where $f_{n}\left( x,y\right) $ is the simple symmetric function $% f_{n}\left( x,y\right) =\sum_{i=0}^{n-1}x^{n-i}y^{i}.$ By induction we can get easily the following lemma. \begin{lemma} \label{lem3}For $n>0,$% \begin{equation*} H^{n}\left( r_{1},r_{2},r_{3},r_{4}\right) =W_{n}. \end{equation*} \end{lemma} Now we are going to give our first result for the even subscripted weighted sums. \begin{theorem} For $n,r>0$, \begin{equation*} \sum\limits_{i=1}^{n}\left( n-i\right) U_{2ri}=\frac{n\left( 2U_{2r}-U_{4r}\right) +U_{2r\left( n+1\right) }-2U_{2nr}+U_{2r\left( n-1\right) }}{\left( U_{4r}-2\right) ^{2}} \end{equation*} \end{theorem} \begin{proof} Solving the following equation% \begin{equation*} D_{2r}\Lambda =\Lambda H\left( 1,\alpha ^{2r},\beta ^{2r},1\right) , \end{equation*}% we obtain the solution depending on one parameter. By taking the parameter as $1,$ we find the matrix $\Lambda $ as follows:% \begin{equation*} \Lambda =\left[ \begin{array}{cccc} V_{4r}+V_{2r}+6 & \alpha ^{6r} & \beta ^{6r} & 1 \\ V_{2r}+5 & \alpha ^{4r} & \beta ^{4r} & 1 \\ 4 & \alpha ^{2r} & \beta ^{2r} & 1 \\ 1 & 1 & 1 & 1% \end{array}% \right] . \end{equation*}% By a simple computation, we obtain $\det \Lambda =\left( 2U_{2r}-U_{4r}\right) \delta $ where $\delta =\sqrt{A^{2}-4}.$ Since $\det \Lambda \not=0,$ we write \begin{equation*} D_{2r}^{n}\Lambda =\Lambda H\left( 1,\alpha ^{2r},\beta ^{2r},1\right) ^{n}. \end{equation*}% By Lemma~\ref{lem3}, the $n$th power of the matrix $H\left( 1,\alpha ^{2r},\beta ^{2r},1\right) $ is given by% \begin{equation*} H\left( 1,\alpha ^{2r},\beta ^{2r},1\right) ^{n}=\left[ \begin{array}{cccc} 1 & 0 & 0 & 0 \\ \sum_{i=0}^{n-1}\alpha ^{2ri} & \alpha ^{2nr} & 0 & 0 \\ \sum_{i=0}^{n-1}\beta ^{2ri} & 0 & \beta ^{2nr} & 0 \\ n & 0 & 0 & 1% \end{array}% \right] . \end{equation*}% Arranging the right side of $D_{2r}^{n}\Lambda =\Lambda H\left( 1,\alpha ^{2r},\beta ^{2r},1\right) ^{n},$ we have the following linear system:% \begin{eqnarray*} \left( V_{4r}+V_{2r}+6\right) d_{11}+\left( V_{2r}+5\right) d_{12}+4d_{13}+d_{14} &=&6+n+\sum\nolimits_{i=0}^{n+2}V_{2ir} \\ \alpha ^{6r}d_{11}+\alpha ^{4r}d_{12}+\alpha ^{2r}d_{13}+d_{24} &=&\alpha ^{2nr+6r} \\ \beta ^{6r}d_{11}+\beta ^{4r}d_{12}+\beta ^{2r}d_{13}+d_{34} &=&\beta ^{2nr+6r} \\ d_{11}+d_{12}+d_{13}+d_{14} &=&1 \end{eqnarray*}% where $D_{2r}=\left[ d_{ij}\right] .$ By the Cramer solution of the above system and using \eqref{E-1}, we get \begin{equation*} d_{11}=\frac{B_{n+2,2r}}{B_{2,2r}}=\frac{\left( \left( n+2\right) \left( 2U_{2r}-U_{4r}\right) +U_{2nr+6r}-2U_{2nr+4r}+U_{2nr+2r}\right) }{\left( U_{4r}-2U_{2r}\right) ^{2}} \end{equation*}% and so \begin{equation*} \sum\limits_{i=1}^{n}\left( n-i\right) U_{2ri}=\frac{n\left( 2U_{2r}-U_{4r}\right) +U_{2r\left( n+1\right) }-2U_{2nr}+U_{2r\left( n-1\right) }}{\left( U_{4r}-2\right) ^{2}}. \end{equation*} \end{proof} As an example, we get% \begin{equation*} \sum\limits_{i=1}^{n}\left( n-i\right) F_{8i}=\frac{n\left( 2F_{8}-F_{16}\right) +F_{8\left( n+1\right) }-2F_{8n}+F_{8\left( n-1\right) }% }{\left( F_{16}-2\right) ^{2}}. \end{equation*} Second, we derive a new formula for the odd subscripted weighted sums by the following Theorem. \begin{theorem} For $n,r>0,$% \begin{equation*} \sum\limits_{i=1}^{n}\left( n-i\right) U_{\left( 2r+1\right) i}=\frac{% U_{\left( n+1\right) \left( 2r+1\right) }+2U_{n\left( 2r+1\right) }+U_{\left( n-1\right) \left( 2r+1\right) }-nU_{2\left( 2r+1\right) }-2U_{2r+1}}{V_{2r+1}^{2}}. \end{equation*} \end{theorem} \begin{proof} Solving the following equation% \begin{equation*} D_{2r+1}\Lambda _{1}=\Lambda _{1}H\left( 1,\alpha ^{2r+1},\beta ^{2r+1},1\right) \end{equation*}% we obtain the solution with one parameter. By taking the parameter as $1,$ we find \begin{equation*} \Lambda _{1}=\left[ \begin{array}{cccc} V_{4r+2}+V_{2r+1}+6 & \alpha ^{6r+3} & \beta ^{6r+3} & 1 \\ V_{2r+1}+5 & \alpha ^{4r+2} & \beta ^{4r+2} & 1 \\ 4 & \alpha ^{2r+1} & \beta ^{2r+1} & 1 \\ 1 & 1 & 1 & 1% \end{array}% \right] . \end{equation*}% Since $\det \Lambda _{1}=U_{4r+2}V_{2r+1}\delta \not=0$ where $\delta =\sqrt{% A^{2}-4},$ we write \begin{equation*} D_{2r}^{n}\Lambda _{1}=\Lambda _{1}H\left( 1,\alpha ^{2r},\beta ^{2r},1\right) ^{n}. \end{equation*}% By Lemma~\ref{lem3}, the $n$th power of matrix $H\left( 1,\alpha ^{2r+1},\beta ^{2r+1},1\right) $ is as follows:% \begin{equation*} H\left( 1,\alpha ^{2r+1},\beta ^{2r+1},1\right) ^{n}=\left[ \begin{array}{cccc} 1 & 0 & 0 & 0 \\ \sum_{i=0}^{n-1}\alpha ^{\left( 2r+1\right) i} & \alpha ^{n\left( 2r+1\right) } & 0 & 0 \\ \sum_{i=0}^{n-1}\beta ^{\left( 2r+1\right) i} & 0 & \beta ^{n\left( 2r+1\right) } & 0 \\ n & 0 & 0 & 1% \end{array}% \right] . \end{equation*}% Computing the right side of $D_{2r}^{n}\Lambda =\Lambda H\left( 1,\alpha ^{2r},\beta ^{2r},1\right) ^{n},$ we have the following linear system:% \begin{eqnarray*} \left( V_{4r+1}+V_{2r+1}+6\right) d_{11}+\left( V_{2r+1}+5\right) d_{12}+4d_{13}+d_{14} &=&6+n+\sum\nolimits_{i=1}^{n+2}V_{i\left( 2r+1\right) } \\ \alpha ^{6r+3}d_{11}+\alpha ^{4r+2}d_{12}+\alpha ^{2r+1}d_{13}+d_{24} &=&\alpha ^{\left( 2r+1\right) \left( n+3\right) } \\ \beta ^{6r}d_{11}+\beta ^{4r+2}d_{12}+\beta ^{2r+1}d_{13}+d_{34} &=&\beta ^{\left( 2r+1\right) \left( n+3\right) } \\ d_{11}+d_{12}+d_{13}+d_{14} &=&1 \end{eqnarray*}% where $D_{2r}=\left[ d_{ij}\right] .$ By the Cramer solution of the above system and from \eqref{E-2}, we obtain% \begin{eqnarray*} d_{11} &=&\frac{B_{n+2,2r}}{B_{2,2r}} \\ &=&\frac{\delta \left( U_{\left( n+3\right) \left( 2r+1\right) }+2U_{\left( n+2\right) \left( 2r+1\right) }+U_{\left( n+1\right) \left( 2r+1\right) }-\left( n+2\right) U_{2\left( 2r+1\right) }-2U_{2r+1}\right) }{% U_{4r+2}V_{2r+1}\delta } \end{eqnarray*}% and so \begin{equation*} \sum\limits_{i=1}^{n}\left( n-i\right) U_{\left( 2r+1\right) i}=\frac{% U_{\left( n+1\right) \left( 2r+1\right) }+2U_{n\left( 2r+1\right) }+U_{\left( n-1\right) \left( 2r+1\right) }-nU_{2\left( 2r+1\right) }-2U_{2r+1}}{V_{2r+1}^{2}}. \end{equation*}% Thus the theorem is proved. \end{proof} As an example of the above theorem, we mention \begin{equation*} \sum\limits_{i=1}^{n}\left( n-i\right) F_{5i}=\frac{F_{5\left( n+1\right) }+2F_{5n}+F_{5\left( n-1\right) }-nF_{10}-2F_{5}}{L_{5}^{2}}. \end{equation*} \section{Permanental Representations} This section is mainly devoted to derive relationships between permanents of certain matrices and the terms of the sequence $\left\{ B_{n,t}\right\} .$ For similar relationships between determinants or permanents of certain matrices and terms of certain recurrences, we can refer to \cite{Minc,Strang}% . Define the $n\times n$ $(k-1)-$superdiagonal matrix in the compact form:% \begin{equation*} M_{n}\left( e_{1},e_{2},\ldots ,e_{k}\right) =\left[ \begin{array}{ccccccc} e_{1} & e_{2} & \ldots & e_{k} & & & 0 \\ 1 & e_{1} & e_{2} & \ldots & e_{k} & & \\ & 1 & \ddots & \ddots & \ddots & \ddots & \\ & & \ddots & e_{1} & e_{2} & \ldots & e_{k} \\ & & & 1 & e_{1} & e_{2} & \vdots \\ & & & & 1 & e_{1} & e_{2} \\ 0 & & & & & 1 & e_{1}% \end{array}% \right] \end{equation*}% where $e_{1},e_{2},\ldots ,e_{k}$ are arbitrary integers. Define the $k$th order linear recurrence $\left\{ z_{n}\right\} $ as follows \begin{equation*} z_{n}=e_{1}z_{n-1}+e_{2}z_{n-2}+\ldots +e_{k}z_{n-k},\ n>0, \end{equation*}% where $z_{1-k}=z_{2-k}=\ldots =z_{-1}=0$ and $z_{0}=1.$ Then we have the following result. \begin{theorem} For $n>0,$% \begin{equation*} \mathrm{per}M_{n}\left( e_{1},e_{2},\ldots ,e_{k}\right) =z_{n} \end{equation*}% where $\mathrm{per}M_{i}=z_{i}$ for $0\leq i\leq k-1.$ \end{theorem} \begin{proof} Denote $\mathrm{per}M_{n}\left( e_{1},e_{2},\ldots ,e_{k}\right) $ by $% \mathrm{per}M_{n}.$ Extending $\mathrm{per}M_{n}$ with respect to the last column by the Laplace expansion of permanent, then we obtain% \begin{equation*} \mathrm{per}M_{n}=e_{1}\mathrm{per}M_{n-1}+e_{2}\mathrm{per}M_{n-2}+\ldots +e_{k}\mathrm{per}M_{n-k}. \end{equation*}% Since the recurrence relations (and initial conditions) of $\mathrm{per}M_{n} $ and the sequence $\left\{ z_{n}\right\} $ are the same, the conclusion easily follows. \end{proof} Denote $4-$tuples $\left( V_{2r}+2,-2\left( V_{2r}+1\right) ,V_{2r}+2,-1\right) $ and $(V_{2r+1}+2,-2V_{2r+1},V_{2r+1}-2,1)$ by $w_{1}$ and $w_{2},$ respectively. Then we have the following corollary. \begin{corollary} For $n>0$ and $r>0,$% \begin{equation*} \mathrm{per} M_{n}\left( v_{1}\right) =\sum\limits_{i=1}^{n}\left( n-i\right) U_{2ir}, \end{equation*}% and for $r\geq 0$ \begin{equation*} \mathrm{per} M_{n}\left( v_{2}\right) =\sum\limits_{i=1}^{n}\left( n-i\right) U_{i\left( 2r+1\right) }. \end{equation*} \end{corollary} \section{Acknowledgments} The second author was partially supported by an NPS-RIP grant. \begin{thebibliography}{9} \bibitem{Chen} W. Y. C. Chen and J.D. Louck, The combinatorial power of the companion matrix, \textit{Linear Algebra Appl.} {\bf 232} (1996), 261--278. \bibitem{Kilic} E. Kilic, Sums of the squares of terms of sequence $\left\{ u_{n}\right\}$, \textit{Proc. Indian Acad. Sci.} (Math. Sci.) {\bf 118} (1) 2008, 27--41. \bibitem{Koshy} T. Koshy, \textit{Fibonacci and Lucas numbers with applications}, Pure and Applied Mathematics Wiley-Interscience, New York, 2001. \bibitem{Minc} H. Minc, Permanents of $(0,1)$-circulants, \textit{Canad. Math. Bull}. {\bf 7} (2) (1964), 253--263. \bibitem{Strang} G. Strang, \textit{Introduction to Linear Algebra}, 3rd ed., Wellesley-Cambridge, Wellesley MA, 2003. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 \textit{Mathematics Subject Classification}: Primary 11B39; Secondary 15A36. \noindent \emph{Keywords: } Second order linear recurrences, weighted sums, generating matrix, permanent, generating functions. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A001924}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received August 19 2008; revised version received February 10 2009. Published in {\it Journal of Integer Sequences}, February 14 2009. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}