Forgive me if this is better suited to MathOverflow, but my question is probably too simple to put there.

I'm reading S.K Lando's Lectures on Generating Functions, which gives this definition of the product of two generating functions A and B:

`A(s)*B(s) = a0*b0 + (a0*b1 + a1*b0)*s + (a0*b2 + a1*b1 + a2*b0)*s^2 ...`

I understand that the s is just formal. But - and I know it's obtuse of me - I can't understand how the pattern of terms combining coefficients should continue. If anyone could just extend the definition to one or two more terms, it would probably help me a lot. Many thanks!

For bonus points, an algorithm in Haskell for multiplying two series (represented as lists of coefficients) would be much appreciated too - but it'd be enough for me just to understand the above definition.

Notice that the sum of the coefficient indices is constant in each term. For example `a0*b0 -> 0+0=0`, while `a0*b1 -> 0+1=1` and `a1*b0 -> 1+0=1`.

Recall the story of young Gauss, who discovered that by summing a list of consecutive numbers with its reverse, we obtain a list of constants. The same trick applies here. We'll just take the first k `a_i` and `b_i` coefficients, reverse the list of `b_i` coefficients, and take the component-wise product of the lists.

Here's some Haskell code to generate the coefficient of `s^i` for `i>=0`, given `i` and the list of `as=[a0,a1,...]` and `bs=[b0,b1,...]`:

``````genCoeff :: [Double] -> [Double] -> Int -> Double
genCoeff as bs i = sum \$ zipWith (*) (take (i+1) as) (reverse (take (i+1) bs))
``````

To generate all of the coefficients, we simply map the partially applied function `genCoeff as bs` onto the list `[0,1,...]`, i.e.

``````genAllCeoffs :: [Double] -> [Double] -> [Double]
genAllCoeffs as bs = map (genCoeff as bs) [0..]
``````

Here is a solution which doesn't use `reverse`:

``````add [] bs = bs

mult :: [Int] -> [Int] -> [Int]
mult [] bs = []   -- note: [] = 0
mult as [] = []
mult (a:as) (b:bs) = (a*b) : add (add (map (*a) bs) (map (*b) as)) (0:mult as bs)

test1 = do
let as = [1,2,3]
bs = [4,5]
putStrLn \$ "as      = " ++ show as
putStrLn \$ "bs      = " ++ show bs
putStrLn \$ "as * bs = " ++ show (mult as bs)
``````

Output:

``````as      = [1,2,3]
bs      = [4,5]
as * bs = [4,13,22,15]
``````

It was derived from the following identity:

``````(a0+a1*x) * (b0 + b1*x) = a0*b0 + a0*b1*x + b0*a1*x + a1*b1*x^2
``````

The correspondences are:

``````a0*b0          <-> a*b
a0*b1*x        <-> map (*a) bs
b0*a1*x        <-> map (*b) as
a1*b1*x^2      <-> (0:mult as bs)
``````

Top