%ctor.tex: 
%%a Plain TeX file by Shalosh B. Ekhad and Doron Zeilberger (x pages)

%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\centerline
{\bf Computing the Generating Function of a C-finite sequence }
\bigskip
\centerline
{\it Dr. Z.}

{\bf Input}: A $C$-finite sequence $a(n)$ that is a solution of a (homogeneous) {\bf linear recurrence equation with constnt coefficient}
$$
a(n)=R_1 a(n-1) + \dots + R_d a(n-d) \quad,
$$
subject to the initial conditions
$$
a(0)=a_0, \dots, a(d-1)=a_{d-1} \quad .
$$


{\bf Note}: this `infinite' sequence is a {\bf finite} object, and we represent it in class as a pair of lists {\tt [INI,REC]} where
$$
INI=[a_0, \dots, a_{d-1}] \quad , \quad REC=[R_1, \dots, R_{d} ] \quad .
$$

The (ordinary) generating function of a sequence $a(n), 0 \leq n < \infty$ is, by definition
$$
f(x) = \sum_{n=0}^{\infty} a(n) x^n \quad .
$$


{\bf How to go from the $C$-finite description to the generating function}

For $n \geq d$ we have
$$
a(n)=R_1 a(n-1) + \dots + R_d a(n-d) \quad,
$$

Hence
$$
f(x)= \sum_{n=0}^{\infty} a(n) x^n
= \sum_{n=0}^{d-1} a(n) x^n \, +  \, \sum_{n=d}^{\infty} a(n) x^n
$$
$$
= \sum_{n=0}^{d-1} a(n) x^n \, +  \, \sum_{n=d}^{\infty} \left ( R_1 a(n-1) + R_2 a(n-2) + \dots + R_d a(n-d) \right ) x^n \quad .
$$
Distributing, we have
$$
f(x)= \sum_{n=0}^{d-1} a(n) x^n \, 
$$
$$
+  \, \sum_{n=d}^{\infty}  R_1 a(n-1)x^{n}
+  \, \sum_{n=d}^{\infty}  R_2 a(n-2)x^{n} + \dots 
+  \, \sum_{n=d}^{\infty}  R_d a(n-d) x^{n} \quad .
$$
Rewritng: we get

$$
f(x)= \sum_{n=0}^{d-1} a(n) x^n \, 
$$
$$
+  \,  R_1 x \sum_{n=d}^{\infty} a(n-1)x^{n-1}
+  \, R_2 x^2 \sum_{n=d}^{\infty}  a(n-2)x^{n-2}  + \dots
+  \, R_d x^d \sum_{n=d}^{\infty}   a(n-d) x^{n-d} \quad .
$$

Changing the index of summation we get
$$
f(x)= \sum_{n=0}^{d-1} a(n) x^n \, 
$$
$$
+  \,  R_1 x \sum_{n=d-1}^{\infty} a(n)x^{n}
+  \, R_2 x^2 \sum_{n=d-2}^{\infty}   a(n)x^{n}  + \dots
+  \, R_d x^d \sum_{n=0}^{\infty}   a(n) x^{n} \quad .
$$
It follows that
$$
f(x)= POLYNOMIAL_{d-1}(x) + (R_1 x+ dots + R_d x^d) f(x) \quad
$$
where  $POLYNOMIAL_{d-1}(x)$ is {\bf some} polynomial of degree $d-1$.
Hence
$$
f(x) (1-  (R_1 x+ dots + R_d x^d) ) =  POLYNOMIAL_{d-1}(x) \quad,
$$
and hence
$$
f(x)=   \frac{POLYNOMIAL_{d-1}(x)}{) (1-  (R_1 x+ dots + R_d x^d) )} \quad .
$$
This explains why $f(x)$ is always a rational function, why its denominator is what it is. As for the numerator, the best way is to find
it empirically as we did in class.

\bigskip


\bigskip
\hrule
\bigskip
Dr. Z. Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. \hfill\break
Email: {\tt ShaloshBEkhad at gmail dot com}   \quad .


\end





