Binomial Convolutions for Rational Power Series

The binomial convolution of two sequences $(a_n)$

and

is the sequence whose $n$

th term is $\sum_{k=0}^{n} \binom{n}{k} a_k b_{n-k}$ . If $(a_n)$

and

have rational generating functions, then so does their binomial convolution. We discuss an efficient method, using resultants, for computing this rational generating function and give several examples involving Fibonacci and tribonacci numbers and related sequences. We then describe a similar method for computing Hadamard products of rational generating functions. Finally, we describe two additional methods for computing binomial convolutions and Hadamard products of rational power series, one using symmetric functions and one using partial fractions.

Binomial Convolutions for Rational Power Series

Ira M. Gessel Department of Mathematics Brandeis University Waltham, MA 02453 USA Ishan Kar College of Letters and Science University of California, Berkeley Berkeley, CA 94720 USA

Ira M. Gessel
Department of Mathematics
Brandeis University
Waltham, MA 02453
USA
Ishan Kar
College of Letters and Science
University of California, Berkeley
Berkeley, CA 94720
USA