%Fibonacci Quarterly

\input amstex
\documentstyle{amsppt}










\headline=               
{\ifnum\pageno=1\hfil
 \else
 \hfil{\tenrm\number\pageno}\hfil
\fi}
\footline={\hfil}
\catcode`\@=11
\redefine\logo@{}
\firstpage@false
\catcode`\@=13
\TagsOnRight
%\NoBlackBoxes
\hfuzz=10pt

\topmatter
\title
some information about the binomial transform
\endtitle

\author Helmut Prodinger \endauthor
\affil 
Department of Algebra and Discrete Mathematics \\
Technical University of Vienna, Austria
\endaffil
\address 
{\rm \flushpar AMS classification: 05A10}\newline
\bigskip\flushpar
TU Vienna
\newline Wiedner Hauptstrasse 8--10
\newline A-1040 Vienna
\newline Austria
\endaddress 
\email proding\@email.tuwien.ac.at
\endemail







\endtopmatter
\document

\define\SS{\bar S}
\redefine\AA{\bar A}


\define\knuth{7}
\define\flaric{2}
\define\kirpro{6}
\define\schmid{8}
\define\jonknu{5}
\define\haukk{4}
\define\gould{3}
\define\flajolet{1}

A few days ago I saw the paper 
\cite{2}.
 I think that I can make some additional
remarks that might not be totally useless for the {\sl Fibonacci 
Community\/}!


Let $(a_n)$ be a given sequence and $\displaystyle{s_n=
\sum_{k=0}^n\binom nk a_k}$. Denoting the respective (ordinary)
generating functions by $A(x)$ and $S(x)$, the paper in question mainly
deals with the consequences of the formula 
$$S(x)=\frac{1}{1-x}A
\big(\frac{x}{1-x}\big).\tag 1 $$

Knuth \cite{\knuth} has introduced the {\sl binomial transform} by
$$
\hat a_n=\sum_{k=0}^n\binom nk(-1)^ka_k,
$$
and it is clear that this is the situation from above. But Philippe 
Flajolet and the present writer
 agreed about 10 years ago  that there are just {\sl 
exponential
generating functions\/} hidden! They have a convolution formula
$$
c_n=\sum_{k=0}^n\binom nk a_kb_{n-k},
$$
and upon choosing the $b_k$'s to be all equal to 1, we have the old 
situation. So, denoting the exponential generating functions by
$\AA(x)$ and $\SS(x)$, we have the even simpler formula
$\SS(x)=e^x\AA(x)$. This can readily be inverted as
$\AA(x)=e^{-x}\SS(x)$, whence
$$
a_n=\sum_{k=0}^n
\binom nk (-1)^{n-k}s_k.
$$
These facts about exponential
generating functions are of course folklore; one particular reference is \cite{\gould}.
\medskip
Flajolet and Richmond \cite{\flaric}, Schmid \cite{\schmid} and
Kirschenhofer and the present writer \cite{\kirpro} all made heavy
use of (1). U.Schmid observed (among other writers) that an
exponential generating function 
will be transformed into an ordinary generating
function by the {\sl Borel transform\/}.
\medskip

Now the {\sl generalization}
$$
s_n=\sum_{k=0}^n\binom nk b^{n-k} c^ka_k
$$
or 
$$
S(x)=\frac{1}{1-bx}A
\big(\frac{cx}{1-bx}\big)
$$
translates into
$$
\SS(x)=e^{bx}\AA(cx).
$$
Since 
$$
\AA(x)=e^{ -\frac bcx}\SS(\frac xc),
$$
we find the inversion formula
$$
a_n=c^{-n}\sum_{k=0}^n
\binom nk (-1)^{n-k}b^{n-k}s_k.
$$

The discussion in Theorem 2 becomes quite transparent, considering
exponential generating functions. It is asked whenever we have
$$
F_{pn+r}=\sum_{k=0}^n\binom nk t^{n-k}s^kF_{qk+r},
$$
where $F_n$ denote Fibonacci numbers. The exponential generating function
of the Fibonacci numbers $F_n$ is
$$
\frac{1}{\sqrt 5}\left(e^{\alpha x}-e^{\beta x}\right),
$$
with the usual $\alpha=(1+\sqrt 5\, )/2$ and $\beta=-1/\alpha=(1-\sqrt 5\, 
)/2$.
More generally, the sequence $F_{pn+r}$ leads to
$$
\frac{1}{\sqrt 5}\left(\alpha^re^{\alpha^p x}-\beta^re^{\beta^p x}\right).
$$
The desired equality means in this language
$$
\frac{1}{\sqrt 5}\left(\alpha^re^{\alpha^p x}-\beta^re^{\beta^p x}\right)
=e^{tx}
\frac{1}{\sqrt 5}\left(\alpha^re^{\alpha^qs x}-\beta^re^{\beta^qs x}\right),
$$
from which we deduce the two equations
$$
\align
\alpha^p&=t+\alpha^qs,\\
\beta^p&=t+\beta^qs.
\endalign
$$
Subtracting them we see
$$
s=\frac{\alpha^p-\beta^p}{\alpha^q-\beta^q}=\frac{F_p}{F_q}.
$$
Further,
$$
t=\alpha^p-\alpha^q\frac{\alpha^p-\beta^p}{\alpha^q-\beta^q}
=(-1)^p\frac{\alpha^{q-p}-\beta^{q-p}}{\alpha^q-\beta^q}
=(-1)^p\frac{F_{q-p}}{F_q}.
$$
To justify this {\sl equating of coefficients\/} we note that the
functions $e^{\lambda x}$ are linearly independent; and the other possibility
of grouping terms from the left and the right side would lead to the
impossible equation $\alpha^r=-\beta^r$.
\medskip

In \cite{2} there is also the modification: What are
the coefficients of
$$
T(x)=A
\big(\frac{cx}{1-bx}\big)?
$$
That means, what is the effect of deleting the first factor? We can answer
this much more generally by considering (with an arbitrary 
complex parameter $d$)
$$
T(x)=\frac{1}{(1-bx)^d}A
\big(\frac{cx}{1-bx}\big).
$$
In this derivation we will use the concept of {\sl residues\/}, interesting
{\sl per se\/}. 

We are using the substitution $w=\dfrac{cx}{1-bx}$ or
$x=\dfrac{w}{c+bw}$. Therefore $1-bx=\dfrac{c}{c+bw}$
and $ dx=\dfrac{c}{(c+bw)^2}dw$ and thus
$$\align
t_n:=[x^n]T(x)&=\frac{1}{2\pi i}\oint\frac{dx}{x^{n+1}}T(x)\\
&=\frac{1}{2\pi i}\oint\frac{dx}{x^{n+1}}\frac{(c+bw)^d}{c^d}A(w)\\
&=\frac{1}{2\pi i}\oint\frac{c\, dw}{(c+bw)^2}
\frac{(c+bw)^{n+1}}{w^{n+1}}\frac{(c+bw)^d}{c^d}A(w)\\
&=c^{1-d}[w^n](c+bw)^{n+d-1}A(w)\\
&=\sum_{k=0}^n\binom{n+d-1}{n-k}b^{n-k}c^ka_k.
\endalign
$$
Since 
$$
A(w)=\Big(\frac{c}{c+bw}\Big)^dT\Big(\frac{w}{c+bw}\Big),
$$
we find in a similar way the inversion formula
$$
a_n=c^{-n}\sum_{k=0}^n\binom{n+d-1}{n-k}(-1)^{n-k}b^{n-k}t_k.
$$






\bigskip

The formula ($1$) is also useful to deal with Knuth's sum \cite{\jonknu,
eq. (7.6)}
$$
u_n=\sum_{k=0}^n\binom nk \Big(-\frac 12\Big)^k\binom{2k}k.
$$
Since
$$
\align
f(x)&:=\sum_{k\ge 0}\Big(-\frac 12\Big)^k\binom{2k}kx^k\\
&=\sum_{k\ge 0}\Big(-\frac x2\Big)^k\binom{2k}k\\
&=\frac{1}{\sqrt{1+2x}},
\endalign
$$
the generating function of the sequence $u_n$ turns out to be
$$
\frac{1}{1-x}\frac{1}{\sqrt{1+2\left(\dfrac{x}{1-x}
\right)}}
=\frac{1}{\sqrt{1-x^2}}=\sum_{n\ge 0}x^{2n}\binom{2n}n4^{-n}.
$$
From this we see that $u_n=2^{-n}\binom n{n/2}$ if $n$ is even,
and $u_n=0$ otherwise.

I communicated this idea to Knuth, and he reported that Herbert Wilf
came to this (or a similar) approach independently. 

\bigskip

The formula (1) has also a {\sl combinatorial interpretation\/}. If, 
for example, $A(x)$ enumerates certain words, so that $a_n$ is the
number of words of length $n$ with a certain property, and we perform
the operation ``fill-in a new letter where and as often you want'',
then the new ``language'' has the generating function $S(x)$. For further
details on such
{\sl combinatorial constructions\/} we refer to \cite{\flajolet}.








\Refs



\ref \no \flajolet \by  P.Flajolet 
\paper 
Mathematical Methods in the Analysis of Algorithms and Data Structures
\jour in: Trends in Theoretical Computer Science, E.B\"orger, Ed.,
Computer Science Press, Rockville, Maryland
\yr 1988 \pages 225--304           
\endref

\ref \no \flaric \by  P.Flajolet and L.B.Richmond
\paper Generalized Digital Trees and Their Difference-Differential Equations
\jour Random Structures and Algorithms
\yr 1992 \pages 305--320        \vol 3      
\endref

\ref\no\gould\paper
Series Transformations for Finding Recurrences for Sequences
\by H.W.Gould\jour Fibonacci Quarterly\vol 28 \yr 1990 \pages 
166--171\endref

\ref\no\haukk\paper
Formal Power Series for Binomial Sums of Sequences of Numbers
\by P.Haukkanen \jour Fibonacci Quarterly\vol 31 \yr 1993 \pages 
28--31\endref

\ref\no\jonknu\by A.Jonassen and D.E.Knuth \paper A Trivial Algorithm
Whose Analysis isn't\jour Journal of Computer and System Sciences
\vol 16 \yr 
1978 \pages 301--322\endref

\ref\no\kirpro \by P.Kirschenhofer and H.Prodinger
\paper The Path Length of Random Skip Lists \jour submitted\yr 1993\endref
\ref \no 
\knuth \by D.E.Knuth \book The Art of Computer Programming Vol.3\publ 
Addison-Wesley \yr 1973 \publaddr Reading, MA \endref

\ref \no\schmid \paper The Average 
CRI-Length of a Tree Collision Resolution Algorithm in Presence of Multiplicity-Dependent Capture Effects\jour Lecture Notes in Computer Science \vol 623 \yr 
1992\pages 223--234\by U.Schmid\endref

\endRefs

\enddocument
