
\documentstyle[oldlfont,a4ams,righttag,ctagsplt,emlines2,12pt]{amsart}
\renewcommand{\baselinestretch}{1.5}
\textwidth15cm

\begin{document}


\date{}
%\maketitle

\begin{center} 
{\Huge{\bf
{On a question of Cooper and Kennedy}
}}
\bigskip
\end{center}


\begin{center}
{\sc Helmut Prodinger\\
Department for Algebra and Discrete Mathematics \\
TU Wien \\
Wiedner Hauptstrasse 8--10/118 \\
A-1040 Wien\\
 Austria \\
\rm email: proding@@rsmb.tuwien.ac.at}
\end{center}
\bigskip

In \cite{CoKe95}, Cooper and Kennedy note the following: If
\begin{equation}
x_n=ax_{n-1}+bx_{n-2}+cx_{n-3}~,
\end{equation}
then
\begin{equation}
x_n^2=Ax_{n-1}^2+Bx_{n-2}^2+Cx_{n-3}^2+Dx_{n-4}^2
+Ex_{n-5}^2+Fx_{n-6}^2~,
\end{equation}
where the coefficients $A,B,C,D,E,F$ may be expressed in terms of
$a,b,c$. 
They ask: \textbf{Is there a similar formula for third powers?}
% Also,
%what about formulas for}
%\begin{equation} \label{example}
%x_n=ax_{n-1}+bx_{n-2}+cx_{n-3}+dx_{n-4}~?
%\end{equation}
%
The answer is: \textbf{YES}. The reason is the following:
Sequences which are solutions of linear recurrences with constant
coefficients have ordinary generating functions which are 
{\sl rational\/}. Conversely, if a rational function has no pole
in $z=0$, its Taylor coefficients fulfill a linear recurrences with 
constant coefficients. If 
\begin{equation}
f:=\sum_{n\ge0}a_nz^n \qquad\text{and} \qquad
g:=\sum_{n\ge0}b_nz^n 
\end{equation}
are two (formal) series, their \textsc{Hadamard} product is defined to
be
\begin{equation}
f\odot g:=\sum_{n\ge0}a_nb_nz^n ~.
\end{equation}
And rational functions are closed under the Hadamard product!
(See \cite[page 85]{Comtet74}.)

The larger (and maybe even more important) class of {\sl holonomic\/}
functions (solutions of linear differential equations with polynomial
coefficients) is also closed under the Hadamard product.
Their Taylor coefficients fulfill linear recursions with polynomial
coefficients. There is a \textsc{Maple} package,  \textsc{Gfun}, 
which computes (among many other useful things) the Hadamard product.
(See \cite{SaZi94}.) 

%As an example, we find for the sequence in 
%(\ref{example}) 
%\begin{equation}
%x_n^2=Ax_{n-1}^2+Bx_{n-2}^2+Cx_{n-3}^2+Dx_{n-4}^2
%+Ex_{n-5}^2+Fx_{n-6}^2+Gx_{n-7}^2+Hx_{n-8}^2~,
%\end{equation}
%with
%


There is another very useful program, \textsc{Ekhad}, written by Doron Zeilberger
(\cite{PeWiZe96}), which should be mentioned. With it, we find for example
recursions for the $d$th powers of the Fibonacci numbers $F_n$
in almost no time. In the following,
$F_n^d$ will be a solution of the given recursion.
\begin{align*}
d=1\qquad & x_{n+2}-x_{n+1}-x_{n}=0\\
d=2\qquad & x_{n+3}-2x_{n+2}-2x_{n+1}+x_{n}=0\\
d=3\qquad & x_{n+4}-3x_{n+3}-6x_{n+2}+3x_{n+1}+x_{n}=0\\
d=4\qquad & x_{n+5}-5x_{n+4}-15x_{n+3}+15x_{n+2}+5x_{n+1}-x_{n}=0\\
d=5\qquad & x_{n+6}-8x_{n+5}-40x_{n+4}+60x_{n+3}+40x_{n+2}-8x_{n+1}-x_{n}=0\\
d=6\qquad & x_{n+7}-13x_{n+6}-104x_{n+5}+260x_{n+4}+260x_{n+3}-104x_{n+2}-13x_{n+1}+x_{n}=0
\end{align*}

\bibliographystyle{plain} 
\begin{thebibliography}{1}
\bibitem{Comtet74}
L.~Comtet.
\newblock {\em Advanced Combinatorics}.
\newblock Reidel, Dordrecht, 1974.

\bibitem{CoKe95}
C.~N. Cooper and R.~E. Kennedy.
\newblock Proof of a result by {J}arden by generalizing a proof of {C}arlitz.
\newblock {\em Fibonacci Quarterly}, 33:304--310, 1995.

\bibitem{PeWiZe96}
M.~Petkovsek, H.~Wilf, and D.~Zeilberger.
\newblock {\em $A=B$}.
\newblock A.K. Peters, Ltd., 1996.

\bibitem{SaZi94}
Bruno Salvy and Paul Zimmermann.
\newblock {GFUN}: a {Maple} package for the manipulation of generating and
  holonomic functions in one variable.
\newblock {\em ACM Transactions on Mathematical Software}, 20(2):163--167,
  1994.

\end{thebibliography}


\bigskip 
\noindent 1991 \textit{Mathematics Subject Classification.}\ {11B37.}

\end{document}

