<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}

\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\&lt;{\langle}
\def\&gt;{\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&gt;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*}
&amp;&amp;\sum\limits_{i=1}^{n}iF_{i}=nF_{n+2}-F_{n+3}+2 \\
&amp;&amp;\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&gt;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&gt;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&gt;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&gt;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*}
&amp;&amp;(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} \\
&amp;=&amp;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} \\
&amp;=&amp;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} \\
&amp;=&amp; 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} \\
&amp;=&amp; 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} \\
&amp;=&amp; 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)} \\
&amp;=&amp; 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*}
&amp;&amp;(V_t+2) B_{n-1,t}-2V_t B_{n-2,t}+ (V_t-2) B_{n-3,t}+B_{n-4,t} \\
&amp;=&amp;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} \\
&amp;=&amp; 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} \\ 
&amp;=&amp; 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} \\
&amp;=&amp; 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&gt;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} &amp; c_{2} &amp; c_{3} &amp; \ldots &amp; c_{k-1} &amp; c_{k} \\
1 &amp; 0 &amp; 0 &amp; \ldots &amp; 0 &amp; 0 \\
0 &amp; 1 &amp; 0 &amp; \ldots &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 1 &amp; \ldots &amp; 0 &amp; 0 \\
\vdots &amp; \vdots &amp; \vdots &amp; \ddots &amp; \vdots &amp; \vdots \\
0 &amp; 0 &amp; 0 &amp; \ldots &amp; 1 &amp; 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&gt;0,$%
\begin{eqnarray*}
&amp;&amp;\sum\limits_{i=1}^{n}\left( n-i\right) U_{2ir} \\
&amp;=&amp;\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*}
&amp;&amp;\sum\limits_{i=1}^{n}\left( n-i\right) U_{i\left( 2r+1\right) } \\
&amp;=&amp;\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&gt;3$ and even $t$ such that $t=2r,$~$r&gt;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&gt;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&gt;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 &amp; -2\left( V_{t}+1\right) &amp; V_{t}+2 &amp; -1 \\
1 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 1 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 1 &amp; 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} &amp; H_{n+1,t} &amp; Q_{n+2,t} &amp; -B_{n+1,t} \\
B_{n+1,t} &amp; H_{n,t} &amp; Q_{n+1,t} &amp; -B_{n,t} \\
B_{n,t} &amp; H_{n-1,t} &amp; Q_{n,t} &amp; -B_{n-1,t} \\
B_{n-1,t} &amp; H_{n-2,t} &amp; Q_{n-1,t} &amp; -B_{n-2,t}%
\end{array}%
\right]
\end{equation}%
and%
\begin{equation*}
\text{ }D_{t}=\left[
\begin{array}{cccc}
V_{2r}+2 &amp; -2\left( V_{2r}+1\right) &amp; V_{2r}+2 &amp; -1 \\
1 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 1 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 1 &amp; 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&gt;3$ and $r&gt;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&gt;1,k&gt;0$. Without effort we obtain

\begin{corollary}
\label{cor2} For $n,k&gt;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&gt;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&gt;3,  \label{rec4}
\end{equation}%
and
\begin{equation}
H_{n,t}=-2V_{t}B_{n,t}+Q_{n,t},\ n&gt;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 &amp; -2V_{2r+1} &amp; V_{2r+1}-2 &amp; 1 \\
1 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 1 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 1 &amp; 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&gt;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} &amp; 0 &amp; 0 &amp; 0 \\
1 &amp; r_{2} &amp; 0 &amp; 0 \\
1 &amp; 0 &amp; r_{3} &amp; 0 \\
1 &amp; 0 &amp; 0 &amp; r_{4}%
\end{array}%
\right]
\end{equation*}
and
\begin{equation*}
W_{n}=\left[
\begin{array}{cccc}
r_{1}^{n} &amp; 0 &amp; 0 &amp; 0 \\
f_{n}\left( r_{1},r_{2}\right) &amp; r_{2}^{n} &amp; 0 &amp; 0 \\
f_{n}\left( r_{1},r_{3}\right) &amp; 0 &amp; r_{3}^{n} &amp; 0 \\
f_{n}\left( r_{1},r_{4}\right) &amp; 0 &amp; 0 &amp; r_{4}^{n}%
\end{array}%
\right],\ n&gt;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&gt;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&gt;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 &amp; \alpha ^{6r} &amp; \beta ^{6r} &amp; 1 \\
V_{2r}+5 &amp; \alpha ^{4r} &amp; \beta ^{4r} &amp; 1 \\
4 &amp; \alpha ^{2r} &amp; \beta ^{2r} &amp; 1 \\
1 &amp; 1 &amp; 1 &amp; 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 &amp; 0 &amp; 0 &amp; 0 \\
\sum_{i=0}^{n-1}\alpha ^{2ri} &amp; \alpha ^{2nr} &amp; 0 &amp; 0 \\
\sum_{i=0}^{n-1}\beta ^{2ri} &amp; 0 &amp; \beta ^{2nr} &amp; 0 \\
n &amp; 0 &amp; 0 &amp; 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} &amp;=&amp;6+n+\sum\nolimits_{i=0}^{n+2}V_{2ir} \\
\alpha ^{6r}d_{11}+\alpha ^{4r}d_{12}+\alpha ^{2r}d_{13}+d_{24} &amp;=&amp;\alpha
^{2nr+6r} \\
\beta ^{6r}d_{11}+\beta ^{4r}d_{12}+\beta ^{2r}d_{13}+d_{34} &amp;=&amp;\beta
^{2nr+6r} \\
d_{11}+d_{12}+d_{13}+d_{14} &amp;=&amp;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&gt;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 &amp; \alpha ^{6r+3} &amp; \beta ^{6r+3} &amp; 1 \\
V_{2r+1}+5 &amp; \alpha ^{4r+2} &amp; \beta ^{4r+2} &amp; 1 \\
4 &amp; \alpha ^{2r+1} &amp; \beta ^{2r+1} &amp; 1 \\
1 &amp; 1 &amp; 1 &amp; 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 &amp; 0 &amp; 0 &amp; 0 \\
\sum_{i=0}^{n-1}\alpha ^{\left( 2r+1\right) i} &amp; \alpha ^{n\left(
2r+1\right) } &amp; 0 &amp; 0 \\
\sum_{i=0}^{n-1}\beta ^{\left( 2r+1\right) i} &amp; 0 &amp; \beta ^{n\left(
2r+1\right) } &amp; 0 \\
n &amp; 0 &amp; 0 &amp; 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} &amp;=&amp;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}
&amp;=&amp;\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} &amp;=&amp;\beta
^{\left( 2r+1\right) \left( n+3\right) } \\
d_{11}+d_{12}+d_{13}+d_{14} &amp;=&amp;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} &amp;=&amp;\frac{B_{n+2,2r}}{B_{2,2r}} \\
&amp;=&amp;\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} &amp; e_{2} &amp; \ldots  &amp; e_{k} &amp;  &amp;  &amp; 0 \\
1 &amp; e_{1} &amp; e_{2} &amp; \ldots  &amp; e_{k} &amp;  &amp;  \\
&amp; 1 &amp; \ddots  &amp; \ddots  &amp; \ddots  &amp; \ddots  &amp;  \\
&amp;  &amp; \ddots  &amp; e_{1} &amp; e_{2} &amp; \ldots  &amp; e_{k} \\
&amp;  &amp;  &amp; 1 &amp; e_{1} &amp; e_{2} &amp; \vdots  \\
&amp;  &amp;  &amp;  &amp; 1 &amp; e_{1} &amp; e_{2} \\
0 &amp;  &amp;  &amp;  &amp;  &amp; 1 &amp; 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&gt;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&gt;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&gt;0$ and $r&gt;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}

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