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
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
i and the list of
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
genAllCeoffs :: [Double] -> [Double] -> [Double] genAllCoeffs as bs = map (genCoeff as bs) [0..]
Here is a solution which doesn't use
add  bs = bs add as  = as add (a:as) (b:bs) = (a+b) : add as 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)
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)