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

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf Sum Relations for Lucas
Sequences\footnote{Supported by the National Natural Science
Foundation of China (No.\ 10671155).}} \vskip 1cm
\large Yuan He and Wenpeng Zhang\\
Department of Mathematics \\
Northwest University\\
Xi'an 710069 \\
P. R. China\\
\href{mailto:hyyhe@yahoo.com.cn}{\tt hyyhe@yahoo.com.cn}\\
\href{mailto:wpzhang@nwu.edu.cn}{\tt wpzhang@nwu.edu.cn}\\
\end{center}

\vskip .2 in

\begin{abstract}
In this paper, we establish four sum relations for Lucas sequences.
As applications, we derive some combinatorial identities involving
Lucas sequences that extend some known results.
\end{abstract}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}


\section{Introduction}

Given two integer parameters $P$ and $Q$, the Lucas sequences of the
first kind $U_{n}=U_{n}(P,Q)$ $(n\in\mathbb{N})$ and of the second
kind $V_{n}=V_{n}(P,Q)$ $(n\in\mathbb{N})$ are defined by the
recurrence relations
\begin{equation}\label{eq:101}
U_{0}=0,\quad U_{1}=1,\quad\text{and}\quad
U_{n}=PU_{n-1}-QU_{n-2}~(n\geq2),
\end{equation}
\begin{equation}\label{eq:102}
V_{0}=2,\quad V_{1}=p,\quad\text{and}\quad
V_{n}=PV_{n-1}-QV_{n-2}~(n\geq2).
\end{equation}
The characteristic equation $x^{2}-Px+Q=0$ of the sequences $U_{n}$
and $V_{n}$ has two roots $\alpha=(P+\sqrt{D})/2$ and
$\beta=(P-\sqrt{D})/2$ with the discriminant $D=P^{2}-4Q$. Note that
$D^{1/2}=\alpha-\beta$. Furthermore, $D=0$ means $x^{2}-Px+Q=0$ has
the repeated root $\alpha=\beta=P/2$. It is well known that for any
$n\in\mathbb{N}$ (see \cite[pp.\ 41--44]{ribenboim2}),
\begin{equation}\label{eq:103}
PU_{n}+V_{n}=2U_{n+1},\quad
(\alpha-\beta)U_{n}=\alpha^{n}-\beta^{n},\quad
V_{n}=\alpha^{n}+\beta^{n}.
\end{equation}
The Lucas sequences $U_{n}$ and $V_{n}$ can be regarded as the
generalization of many integer sequences, for example, $F_{n}$,
$L_{n}$, $P_{n}$, $Q_{n}$, $J_{n}$, and $j_{n}$, known as the
Fibonacci, Lucas, Pell, Pell-Lucas, Jacobsthal, and Jacobsthal-Lucas
numbers, according to whether $P=1,Q=-1$, $P=2,Q=-1$, or $P=1,
Q=-2$; see \cite{sloane} for a good introduction. These numbers play
important roles in many different areas of mathematics, so their
numerous elegant properties have been studied by many authors, see
for example, \cite{ribenboim1,ribenboim2}.

The idea of the present paper stems from the familiar combinatorial
theorem about sets called the principle of cross-classification. We
establish four sum relations for the Lucas sequences as follows.

\begin{theorem}\label{thm:101} Let $n$ be a positive integer, and let $s_{1},s_{2},\ldots,s_{n}$ be any non-negative integers. Then
\begin{eqnarray}\label{eq:104}
&&-\sum_{1\leq i\leq n}\frac{U_{s_{i}}}{\alpha^{s_{i}}}+\sum_{1\leq
i<j\leq n}\frac{U_{s_{i}+s_{j}}}{\alpha^{s_{i}+s_{j}}}-\sum_{1\leq
i<j<k\leq n}\frac{U_{s_{i}+s_{j}+s_{k}}}{\alpha^{s_{i}+s_{j}+s_{k}}}
+\cdots+(-1)^{n}\frac{U_{s_{1}+s_{2}+\cdots+s_{n}}}{\alpha^{s_{1}+s_{2}+\cdots+s_{n}}}\nonumber\\
&&=-D^{\frac{n-1}{2}} \frac{U_{s_{1}}U_{s_{2}}\cdots
U_{s_{n}}}{\alpha^{s_{1}+s_{2}+\cdots+s_{n}}},
\end{eqnarray}
\begin{eqnarray}\label{eq:105}
&&-\sum_{1\leq i\leq n}\frac{U_{s_{i}}}{\beta^{s_{i}}}+\sum_{1\leq
i<j\leq n}\frac{U_{s_{i}+s_{j}}}{\beta^{s_{i}+s_{j}}}-\sum_{1\leq
i<j<k\leq n}\frac{U_{s_{i}+s_{j}+s_{k}}}{\beta^{s_{i}+s_{j}+s_{k}}}
+\cdots+(-1)^{n}\frac{U_{s_{1}+s_{2}+\cdots+s_{n}}}{\beta^{s_{1}+s_{2}+\cdots+s_{n}}}\nonumber\\
&&=(-1)^{n}D^{\frac{n-1}{2}} \frac{U_{s_{1}}U_{s_{2}}\cdots
U_{s_{n}}}{\beta^{s_{1}+s_{2}+\cdots+s_{n}}},
\end{eqnarray}
\begin{eqnarray}\label{eq:106}
&&\sum_{1\leq i\leq n}\frac{V_{s_{i}}}{\alpha^{s_{i}}}+\sum_{1\leq
i<j\leq n}\frac{V_{s_{i}+s_{j}}}{\alpha^{s_{i}+s_{j}}}+\sum_{1\leq
i<j<k\leq n}\frac{V_{s_{i}+s_{j}+s_{k}}}{\alpha^{s_{i}+s_{j}+s_{k}}}
+\cdots+\frac{V_{s_{1}+s_{2}+\cdots+s_{n}}}{\alpha^{s_{1}+s_{2}+\cdots+s_{n}}}\nonumber\\
&&=2^{n}-2+\frac{V_{s_{1}}V_{s_{2}}\cdots
V_{s_{n}}}{\alpha^{s_{1}+s_{2}+\cdots+s_{n}}},
\end{eqnarray}
\begin{eqnarray}\label{eq:107}
&&\sum_{1\leq i\leq n}\frac{V_{s_{i}}}{\beta^{s_{i}}}+\sum_{1\leq
i<j\leq n}\frac{V_{s_{i}+s_{j}}}{\beta^{s_{i}+s_{j}}}+\sum_{1\leq
i<j<k\leq n}\frac{V_{s_{i}+s_{j}+s_{k}}}{\beta^{s_{i}+s_{j}+s_{k}}}
+\cdots+\frac{V_{s_{1}+s_{2}+\cdots+s_{n}}}{\beta^{s_{1}+s_{2}+\cdots+s_{n}}}\nonumber\\
&&=2^{n}-2+\frac{V_{s_{1}}V_{s_{2}}\cdots
V_{s_{n}}}{\beta^{s_{1}+s_{2}+\cdots+s_{n}}}.
\end{eqnarray}
\end{theorem}

Theorem~\ref{thm:101} has some applications and can be deduced as
the generalization of some known results. In section~\ref{sec:2}, we
shall make use of Theorem~\ref{thm:101} to illustrate its
effectiveness. In section~\ref{sec:3}, we shall give the proof of
Theorem~\ref{thm:101}.

\section{Some applications of Theorem~\ref{thm:101}\label{sec:2}}

\begin{theorem}\label{thm:202} Let $n$ be a positive integer, and let
$C_{n}=U_{n}/Q^{n}$, $D_{n}=V_{n}/Q^{n}$, $E_{n}=U_{n}^{2}/Q^{n}$,
$F_{n}=U_{n}V_{n}/Q^{n}$, $G_{n}=V_{n}^{2}/Q^{n}$. Suppose that the
discriminant $D$ is not equal to $0$. Then, for non-negative
integers $s_{1},s_{2},\ldots,s_{n}$,
\begin{eqnarray}\label{eq:208}
&&-\sum_{1\leq i\leq n}E_{s_{i}}+\sum_{1\leq i<j\leq
n}E_{s_{i}+s_{j}}-\sum_{1\leq i<j<k\leq n}E_{s_{i}+s_{j}+s_{k}}
+\cdots+(-1)^{n}E_{s_{1}+s_{2}+\cdots+s_{n}}\nonumber\\
&&=\begin{cases}
D^{\frac{n-2}{2}}D_{s_{1}+s_{2}+\cdots+s_{n}}U_{s_{1}}U_{s_{2}}\cdots
U_{s_{n}},&2\mid n,\\
-D^{\frac{n-1}{2}}C_{s_{1}+s_{2}+\cdots+s_{n}}U_{s_{1}}U_{s_{2}}\cdots
U_{s_{n}},&2\nmid n,\\
\end{cases}
\end{eqnarray}
\begin{eqnarray}\label{eq:209}
&&-\sum_{1\leq i\leq n}F_{s_{i}}+\sum_{1\leq i<j\leq
n}F_{s_{i}+s_{j}}-\sum_{1\leq i<j<k\leq n}F_{s_{i}+s_{j}+s_{k}}
+\cdots+(-1)^{n}F_{s_{1}+s_{2}+\cdots+s_{n}}\nonumber\\
&&=\begin{cases}
D^{\frac{n}{2}}C_{s_{1}+s_{2}+\cdots+s_{n}}U_{s_{1}}U_{s_{2}}\cdots
U_{s_{n}},&2\mid n,\\
-D^{\frac{n-1}{2}}D_{s_{1}+s_{2}+\cdots+s_{n}}U_{s_{1}}U_{s_{2}}\cdots
U_{s_{n}},&2\nmid n,\\
\end{cases}
\end{eqnarray}
\begin{eqnarray}\label{eq:210}
&&\sum_{1\leq i\leq n}F_{s_{i}}+\sum_{1\leq i<j\leq
n}F_{s_{i}+s_{j}}+\sum_{1\leq i<j<k\leq n}F_{s_{i}+s_{j}+s_{k}}
+\cdots+F_{s_{1}+s_{2}+\cdots+s_{n}}\nonumber\\
&&=C_{s_{1}+s_{2}+\cdots+s_{n}}V_{s_{1}}V_{s_{2}}\cdots V_{s_{n}},
\end{eqnarray}
\begin{eqnarray}\label{eq:211}
&&\sum_{1\leq i\leq n}G_{s_{i}}+\sum_{1\leq i<j\leq
n}G_{s_{i}+s_{j}}+\sum_{1\leq i<j<k\leq n}G_{s_{i}+s_{j}+s_{k}}
+\cdots+G_{s_{1}+s_{2}+\cdots+s_{n}}\nonumber\\
&&=2^{n+1}-4+D_{s_{1}+s_{2}+\cdots+s_{n}}V_{s_{1}}V_{s_{2}}\cdots
V_{s_{n}}.
\end{eqnarray}
\end{theorem}

\begin{proof}
Adding and subtracting $(\ref{eq:104})$ and $(\ref{eq:105})$, and
$(\ref{eq:106})$ and $(\ref{eq:107})$, respectively, we are done by
applying the last two identities of $(\ref{eq:103})$.
\end{proof}

\begin{corollary}\label{cor:203} Let $n$ be a positive integer, and let $k$ be a non-negative integer. Suppose that the
discriminant $D$ is not equal to 0. Then
\begin{equation}\label{eq:212}
\sum_{i=0}^{n}\binom{n}{i}Q^{(n-i)k}U_{ik}V_{ik}= U_{kn}V_{k}^{n},
\end{equation}
\begin{equation}\label{eq:213}
\sum_{i=0}^{n}\binom{n}{i}Q^{(n-i)k}V_{ik}^{2}=2^{n+1}Q^{nk}+V_{kn}V_{k}^{n},
\end{equation}
\begin{equation}\label{eq:214}
\sum_{i=0}^{n}\binom{n}{i}(-1)^{i}Q^{(n-i)k}U_{ik}^{2}=
\begin{cases}
D^{\frac{n-2}{2}}V_{kn}U_{k}^{n},&\text{$2\mid n$},\\
-D^{\frac{n-1}{2}}U_{kn}U_{k}^{n},&\text{$2\nmid n$},\\
\end{cases}
\end{equation}
\begin{equation}\label{eq:215}
\sum_{i=0}^{n}\binom{n}{i}(-1)^{i}Q^{(n-i)k}U_{ik}V_{ik}=
\begin{cases}
D^{\frac{n}{2}}U_{kn}U_{k}^{n},&2\mid n,\\
-D^{\frac{n-1}{2}}V_{kn}U_{k}^{n},&\text{$2\nmid n$}.\\
\end{cases}
\end{equation}
\end{corollary}

\begin{proof}
Setting $s_{1}=s_{2}=\cdots=s_{n}=k$ in Theorem~\ref{thm:202}, the
desired results follow.
\end{proof}

\begin{remark}
By the last two identities of $(\ref{eq:103})$, one can easily check
that if the discriminant $D\not=0$ then $U_{n}V_{n}=U_{2n}$,
$V_{n}^{2}=V_{2n}+2Q^{n}$, $U_{n}^{2}=(V_{2n}-2Q^{n})/D$, which
together with Corollary~\ref{cor:203} deduce some interesting
results. The case $k$ being an even number in $(\ref{eq:212})$ gives
a sophisticated identity for Fibonacci and Lucas numbers which was
asked by Hoggatt as an advanced problem in \cite{hoggatt}. The case
$k=1$ in $(\ref{eq:214})$ and $(\ref{eq:215})$ give the familiar
combinatorial identities for Fibonacci and Lucas numbers, see for
example, \cite{knott,vajda}.
\end{remark}

\begin{theorem}\label{thm:204} Let $n$ be a positive
integer, let $s_{1},s_{2},\ldots,s_{n}$ be any non-negative integers
such that $s_{1}+s_{2}+\cdots+s_{n}=s$, and let
$C_{m,n}=U_{m}U_{n-m}$, $D_{m,n}=U_{m}V_{n-m}$,
$E_{m,n}=V_{m}U_{n-m}$, $F_{m,n}=V_{m}V_{n-m}$. Suppose that the
discriminant $D$ is not equal to 0. Then
\begin{eqnarray}\label{eq:216}
&&-\sum_{1\leq i\leq n}C_{s_{i},s}+\sum_{1\leq i<j\leq
n}C_{s_{i}+s_{j},s}-\sum_{1\leq i<j<k\leq n}C_{s_{i}+s_{j}+s_{k},s}
+\cdots+(-1)^{n}C_{s,s}\nonumber\\&&=\begin{cases}
-2D^{\frac{n-2}{2}}U_{s_{1}}U_{s_{2}}\cdots
U_{s_{n}},&2\mid n,\\
0,&2\nmid n,\\
\end{cases}
\end{eqnarray}
\begin{eqnarray}\label{eq:217}
&&-\sum_{1\leq i\leq n}D_{s_{i},s}+\sum_{1\leq i<j\leq
n}D_{s_{i}+s_{j},s}-\sum_{1\leq i<j<k\leq n}D_{s_{i}+s_{j}+s_{k},s}
+\cdots+(-1)^{n}D_{s,s}\nonumber\\
&&=\begin{cases}
0,&2\mid n,\\
-2D^{\frac{n-1}{2}}U_{s_{1}}U_{s_{2}}\cdots
U_{s_{n}},&2\nmid n,\\
\end{cases}
\end{eqnarray}
\begin{eqnarray}\label{eq:218}
&&\sum_{1\leq i\leq n}E_{s_{i},s}+\sum_{1\leq i<j\leq
n}E_{s_{i}+s_{j},s}+\sum_{1\leq i<j<k\leq
n}E_{s_{i}+s_{j}+s_{k},s}+\cdots+E_{s,s}\nonumber\\&&=(2^{n}-2)U_{s},
\end{eqnarray}
\begin{eqnarray}\label{eq:219}
&&\sum_{1\leq i\leq n}F_{s_{i},s}+\sum_{1\leq i<j\leq
n}F_{s_{i}+s_{j},s}+\sum_{1\leq i<j<k\leq
n}F_{s_{i}+s_{j}+s_{k},s}+\cdots+F_{s,s}\nonumber\\&&=(2^{n}-2)V_{s}+2V_{s_{1}}V_{s_{2}}\cdots
V_{s_{n}}.
\end{eqnarray}
\end{theorem}

\begin{proof}
Multiplying $\alpha^{s}$ in the both sides of $(\ref{eq:104})$ and
$(\ref{eq:106})$, $\beta^{s}$ in the both sides of $(\ref{eq:105})$
and $(\ref{eq:107})$, and then adding and subtracting
$(\ref{eq:104})$ and $(\ref{eq:105})$, and $(\ref{eq:106})$ and
$(\ref{eq:107})$, respectively, the desired results immediately
follow by applying the last two identities of $(\ref{eq:103})$.
\end{proof}

\begin{corollary}\label{cor:205} Let $n$ be a positive integer, and let $k$ be a non-negative integer. Suppose that the
discriminant $D$ is not equal to 0. Then
\begin{equation}\label{eq:220}
\sum_{i=0}^{n}\binom{n}{i}Q^{ik}U_{(n-2i)k}=0,
\end{equation}
\begin{equation}\label{eq:221}
\sum_{i=0}^{n}\binom{n}{i}Q^{ik}V_{(n-2i)k}=2V_{k}^{n},
\end{equation}
\begin{equation}\label{eq:222}
\sum_{i=0}^{n}\binom{n}{i}(-1)^{i}Q^{ik}V_{(n-2i)k}=\begin{cases}
2D^{\frac{n}{2}}U_{k}^{n},&2\mid n,\\
0,&2\nmid n,
\end{cases}
\end{equation}
\begin{equation}\label{eq:223}
\sum_{i=0}^{n}\binom{n}{i}(-1)^{i}Q^{ik}U_{(n-2i)k} =\begin{cases}
0,&2\mid n,\\
2D^{\frac{n-1}{2}}U_{k}^{n},&2\nmid n.\\
\end{cases}
\end{equation}
\end{corollary}

\begin{proof}
By the last two identities of $(\ref{eq:103})$, one can easily check
that if the discriminant $D\not=0$ then
$V_{ik}U_{(n-i)k}=U_{kn}+Q^{ik}U_{(n-2i)k}$,
$V_{ik}V_{(n-i)k}=V_{nk}+Q^{ik}V_{(n-2i)k}$,
$U_{ik}U_{(n-i)k}=(V_{nk}-Q^{ik}V_{(n-2i)k})/D$,
$U_{ik}V_{(n-i)k}=U_{nk}-Q^{ik}U_{(n-2i)k}$. Thus, by setting
$s_{1}=s_{2}=\cdots=s_{n}=k$ in Theorem~\ref{thm:204},
Corollary~\ref{cor:205} follows immediately.
\end{proof}

\begin{remark}
The equations $(\ref{eq:221})$--$(\ref{eq:223})$
extend the powers of Fibonacci and Lucas numbers as sums, see for
example, \cite{knott,vajda}.
\end{remark}

\section{The proof of Theorem~\ref{thm:101}\label{sec:3}}
\noindent{\em{The proof of Theorem~\ref{thm:101}.}} Clearly, the
case $n=1$ in Theorem~\ref{thm:101} is complete.

Now, we consider the case $n\geq2$. By $(\ref{eq:103})$, it is easy
to see that if the discriminant $D\not=0$ then
$U_{n}=n\alpha^{n-1}=n\beta^{n-1}$, $V_{n}=2\alpha^{n}=2\beta^{n}$
for all $n\in\mathbb{N}$. Thus, in view of the fact
$\sum_{i=1}^{n}\binom{n}{i}=2^{n}-1$ and for any integer $n\geq2$,
\begin{equation*}
-\sum_{1\leq i\leq n}s_{i}+\sum_{1\leq i<j\leq
n}(s_{i}+s_{j})-\sum_{1\leq i<j<k\leq n}(s_{i}+s_{j}+s_{k})
+\cdots+(-1)^{n}(s_{1}+s_{2}+\cdots+s_{n})=0,
\end{equation*}
Theorem~\ref{thm:101} is complete when the discriminant $D=0$. Next,
we use induction on $n$ to consider the discriminant $D\not=0$.
Applying the last two identities of $(\ref{eq:103})$, we derive
\begin{equation}\label{eq:324}
U_{m}U_{n}=-\frac{U_{m+n}-\alpha^{m}U_{n}-\alpha^{n}U_{m}}{\sqrt{D}},
\end{equation}
\begin{equation}\label{eq:325}
U_{m}U_{n}=\frac{U_{m+n}-\beta^{m}U_{n}-\beta^{n}U_{m}}{\sqrt{D}},
\end{equation}
\begin{equation}\label{eq:326}
V_{m}V_{n}=V_{m+n}+\alpha^{m}V_{n}+\alpha^{n}V_{m}-2\alpha^{m+n},
\end{equation}
\begin{equation}\label{eq:327}
V_{m}V_{n}=V_{m+n}+\beta^{m}V_{n}+\beta^{n}V_{m}-2\beta^{m+n},
\end{equation}
which imply the case $n=2$ in Theorem~\ref{thm:101} is complete.
Assume that $(\ref{eq:104})$ holds for all $2\leq n=m$. Then, by
multiplying $U_{s_{m+1}}/\alpha^{s_{m+1}}$ in the both sides of
$(\ref{eq:104})$, and applying $(\ref{eq:324})$, we obtain
\begin{eqnarray*}
&&-D^{\frac{m}{2}} \frac{U_{s_{1}}U_{s_{2}}\cdots
U_{s_{m}}U_{s_{m+1}}}{\alpha^{s_{1}+s_{2}+\cdots+s_{m}+s_{m+1}}}\\
&&=\sum_{1\leq i\leq
m}\biggl(\frac{U_{s_{i}+s_{m+1}}}{\alpha^{s_{i}+s_{m+1}}}-\frac{U_{s_{i}}}{\alpha^{s_{i}}}
-\frac{U_{s_{m+1}}}{\alpha^{s_{m+1}}}\biggl)\\
&&\quad-\sum_{1\leq i<j\leq
m}\biggl(\frac{U_{s_{i}+s_{j}+s_{m+1}}}{\alpha^{s_{i}+s_{j}+s_{m+1}}}
-\frac{U_{s_{i}+s_{j}}}{\alpha^{s_{i}+s_{j}}}-\frac{U_{s_{m+1}}}{\alpha^{s_{m+1}}}\biggl)\\
&&\quad+\sum_{1\leq i<j<k\leq
m}\biggl(\frac{U_{s_{i}+s_{j}+s_{k}+s_{m+1}}}{\alpha^{s_{i}+s_{j}+s_{k}+s_{m+1}}}
-\frac{U_{s_{i}+s_{j}+s_{k}}}{\alpha^{s_{i}+s_{j}+s_{k}}}-\frac{U_{s_{m+1}}}{\alpha^{s_{m+1}}}\biggl)\\
&&\quad-\cdots-(-1)^{m}\biggl(\frac{U_{s_{1}+s_{2}+\cdots+s_{m}+s_{m+1}}}{\alpha^{s_{1}+s_{2}+\cdots+s_{m}+s_{m+1}}}-
\frac{U_{s_{1}+s_{2}+\cdots+s_{m}}}{\alpha^{s_{1}+s_{2}+\cdots+s_{m}}}-\frac{U_{s_{m+1}}}{\alpha^{s_{m+1}}}\biggl),
\end{eqnarray*}
which together with $\sum_{i=1}^{m}\binom{m}{i}(-1)^{i}=-1$ means
$(\ref{eq:104})$ holds for all $n=m+1$. In a similar consideration,
$(\ref{eq:105})$, $(\ref{eq:106})$ and $(\ref{eq:107})$ hold for all
$n=m+1$. This concludes the induction step. We are done.\hfill
$\Box$\medskip

\section{Acknowledgements}
 The authors would like to thank the
anonymous referees for their valuable suggestions.

\begin{thebibliography}{99}
\bibitem{hoggatt} V. E. Hoggatt, Advanced Problem H--88,
{\it Fibonacci Quart.} {\bf 6} (1968), 253.
\bibitem{knott}R. Knott, Fibonacci and Golden Ratio Formulae.
Available at
\href{http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormulae.html}
{\tt http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormulae.html}.

\bibitem{ribenboim1}P. Ribenboim, {\it My Numbers, My Friends}, Springer-Verlag,
2000.

\bibitem{ribenboim2}P. Ribenboim, {\it The Book of Prime Number Records}, Springer,
1989.

\bibitem{sloane}N. J. A. Sloane, The Online
Encyclopedia of Integer sequences, 
Available at
\href{http://www.research.att.com/$\thicksim$njas/sequences}{\tt
http://www.research.att.com/$\thicksim$njas/sequences}.

\bibitem{vajda}S. Vajda, {\it Fibonacci and Lucas Numbers, and the Golden Section: Theory and Applications}, Ellis Horwood Limited, 1989.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: Primary
05A19; Secondary 11B39.

\noindent {\it Keywords}: Lucas sequence, combinatorial identity,
sum relation.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000032},
\seqnum{A000045},
\seqnum{A000129},
\seqnum{A001045},
\seqnum{A002203}, and
\seqnum{A014551}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in} \noindent Received March 5 2010; revised version received April 6 2010.
Published in {\it Journal of Integer Sequences}, April 9 2010.

\bigskip
\hrule
\bigskip

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



                                                                                
\end{document}