SOME INFORMATION ABOUT THE BINOMIAL TRANSFORM

Helmut Prodinger

Department of Algebra and Discrete Mathematics Technical University of Vienna, Austria

A few days ago I saw the paper [2]. I think that I can make some additional remarks that might not be totally useless for the Fibonacci Community!

Let (a_{n}) be a given sequence and s_{n} = ∑_{k=0}^{n} \binom{n}{k}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(\frac{x}{1 − x}).  (1)

Knuth [7] has introduced the binomial transform by

â_{n} = ∑_{k=0}^{n} \binom{n}{k}(−1)^{k}a_{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 exponential generating functions hidden! They have a convolution formula

c_{n} = ∑_{k=0}^{n} \binom{n}{k}a_{k}b_{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 Ā(x) and S̄(x), we have the even simpler formula S̄(x) = e^{x}Ā(x). This can readily be inverted as Ā(x) = e^{−x}S̄(x), whence

a_{n} = ∑_{k=0}^{n} \binom{n}{k}(−1)^{n−k}s_{k}.

These facts about exponential generating functions are of course folklore; one particular reference is [3].

Flajolet and Richmond [2], Schmid [8] and Kirschenhofer and the present writer [6] 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 Borel transform.

Now the generalization

s_{n} = ∑_{k=0}^{n} \binom{n}{k}b^{n−k}c^{k}a_{k}

or

S(x) = \frac{1}{1 − bx}A(\frac{cx}{1 − bx})

translates into

S̄(x) = e^{bx}Ā(cx).

Since

Ā(x) = e^{− \frac{b}{c} x}S̄(\frac{x}{c}),

we find the inversion formula

a_{n} = c^{−n} ∑_{k=0}^{n} \binom{n}{k}(−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} = ∑_{k=0}^{n} \binom{n}{k}t^{n−k}s^{k}F_{qk+r},

where F_{n} denote Fibonacci numbers. The exponential generating function of the Fibonacci numbers F_{n} is

\frac{1}{\sqrt{5}} (e^{αx} − e^{βx}) ,

with the usual α = (1 + \sqrt{5} )/2 and β = −1/α = (1 − \sqrt{5} )/2. More generally, the sequence F_{pn+r} leads to

\frac{1}{\sqrt{5}} (α^{r}e^{α^{p}x} − β^{r}e^{β^{p}x}) .

The desired equality means in this language

\frac{1}{\sqrt{5}} (α^{r}e^{α^{p}x} − β^{r}e^{β^{p}x}) = e^{tx} \frac{1}{\sqrt{5}} (α^{r}e^{α^{q}sx} − β^{r}e^{β^{q}sx}) ,

from which we deduce the two equations

α^{p} = t + α^{q}s,
β^{p} = t + β^{q}s.

Subtracting them we see

s = \frac{α^{p} − β^{p}}{α^{q} − β^{q}} = \frac{F_{p}}{F_{q}} .

Further,

t = α^{p} − α^{q} \frac{α^{p} − β^{p}}{α^{q} − β^{q}} = (−1)^{p} \frac{α^{q−p} − β^{q−p}}{α^{q} − β^{q}} = (−1)^{p} \frac{F_{q−p}}{F_{q}} .

To justify this equating of coefficients we note that the functions e^{λx} are linearly independent; and the other possibility of grouping terms from the left and the right side would lead to the impossible equation α^{r} = −β^{r}.

In [2] there is also the modification: What are the coefficients of

T (x) = A(\frac{cx}{1 − bx})?

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(\frac{cx}{1 − bx}).

In this derivation we will use the concept of residues, interesting per se. We are using the substitution w = \frac{cx}{1 − bx} or x = \frac{w}{c + bw}. Therefore 1 − bx =

\frac{c}{c + bw} and dx = \frac{c}{(c + bw)^{2}} dw and thus

t_{n} := [x^{n}]T (x) = \frac{1}{2πi} ∮ \frac{dx}{x^{n+1}} T (x)

= \frac{1}{2πi} ∮ \frac{dx}{x^{n+1}} \frac{(c + bw)^{d}}{c^{d}} A(w)

= \frac{1}{2πi} ∮ \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)

= ∑_{k=0}^{n} \binom{n + d − 1}{n − k}b^{n−k}c^{k}a_{k}.

Since

A(w) = (\frac{c}{c + bw} )^{d}T (\frac{w}{c + bw} ),

we find in a similar way the inversion formula

a_{n} = c^{−n} ∑_{k=0}^{n} \binom{n + d − 1}{n − k}(−1)^{n−k}b^{n−k}t_{k}.

The formula (1) is also useful to deal with Knuth’s sum [5, eq. (7.6)]

u_{n} = ∑_{k=0}^{n} \binom{n}{k}( − \frac{1}{2})^{k}\binom{2k}{k}.

Since

f(x) := ∑_{k≥0} ( − \frac{1}{2})^{k}\binom{2k}{k}x^{k}

= ∑_{k≥0} ( − \frac{x}{2})^{k}\binom{2k}{k}

= \frac{1}{\sqrt{1 + 2x}},

the generating function of the sequence u_{n} turns out to be

\frac{1}{1 − x} \frac{1}{\sqrt{1 + 2 (\frac{x}{1 − x})}} = \frac{1}{\sqrt{1 − x^{2}}} = ∑_{n≥0} x^{2n}\binom{2n}{n}4^{−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.

The formula (1) has also a 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 combinatorial constructions we refer to [1].

References

1. P.Flajolet, Mathematical Methods in the Analysis of Algorithms and Data Structures, in: Trends in Theoretical Computer Science, E.Börger, Ed., Computer Science Press, Rockville, Maryland (1988), 225–304.

2. P.Flajolet and L.B.Richmond, Generalized Digital Trees and Their Difference-Differential Equations, Random Structures and Algorithms 3 (1992), 305–320.

3. H.W.Gould, Series Transformations for Finding Recurrences for Sequences, Fibonacci Quarterly 28 (1990), 166–171.

4. P.Haukkanen, Formal Power Series for Binomial Sums of Sequences of Numbers, Fibonacci Quarterly 31 (1993), 28–31.

5. A.Jonassen and D.E.Knuth, A Trivial Algorithm Whose Analysis isn’t, Journal of Computer and System Sciences 16 (1978), 301–322.

6. P.Kirschenhofer and H.Prodinger, The Path Length of Random Skip Lists, submitted (1993).

7. D.E.Knuth, The Art of Computer Programming Vol.3, Addison-Wesley, Reading, MA, 1973.

8. U.Schmid, The Average CRI-Length of a Tree Collision Resolution Algorithm in Presence of Multiplicity-Dependent Capture Effects, Lecture Notes in Computer Science 623 (1992), 223–234.

AMS classification: 05A10

TU Vienna Wiedner Hauptstrasse 8–10 A-1040 Vienna Austria

E-mail address: proding@email.tuwien.ac.at