Lesson 2

Multiplication. \(\mathcal{A}(x)\cdot \mathcal{B}(x)\) is the generating function for the sequence \(\{c_{n}\}\), defined as: \[c_{n}=a_{0}b_{n}+a_{1}b_{n-1}+\dotsb+a_{n}b_{0}=\sum_{l+r=n}a_{l}b_{r} \ .\] The sequence \(\{c_{n}\}\) is called the convolution of the sequences \(\{a_{n}\}\) and \(\{b_{n}\}\).

Convolution allows us to find generating functions for partial sums: if we multiply the sequence \(\{a_{n}\}\) by \((1,1,1,\dotsc)\), then the \(n\)-th term of the resulting sequence will be \(\sum_{i=0}^{n}a_{i}\).

The multiplication rule provides a different perspective on the binomial theorem. How many ways are there to choose \(n\) elements from the set \(\{a_{1}, \dotsc, a_{m}\}\)? The generating function for the set \(\{a_{i}\}\) is simply \(1+x\): there is one way to choose zero elements and one way to choose one element. Thus, the generating function for choosing from \(\{a_{1}, \dotsc, a_{m}\}\) is simply \((1+x)^{m}\). And we, of course, know the coefficient for the corresponding monomial: \[[x^{n}](1+x)^{m} = \binom{m}{n}\ .\]

The neutral element for the multiplication operation we defined is the sequence \(\mathcal{I}(x)=(1,0,0,\dotsc)\). Accordingly, we say that \(\mathcal{B}(x)\) is inverse to \(\mathcal{A}(x)\) if \(\mathcal{A}(x)\cdot \mathcal{B}(x)=\mathcal{I}(x)\). We show that the inverse exists (and is unique in this case) if and only if \(a_{0} \neq 0\). Indeed, for the sequence \(\{b_{n}\}\) to be the inverse of \(\{a_{n}\}\), it is necessary and sufficient that the following (infinite system of equations) holds: \[\begin{align*}1&=a_{0}b_{0}\\ 0&=a_{1}b_{0}+a_{0}b_{1}\\ 0&=a_{2}b_{0}+a_{1}b_{1}+a_{0}b_{2}\\ \vdots\end{align*}\] It is easy to see that \(b_{0}\) is found from the first equation (\(b_{0}=1/a_{0}\)), \(b_{1}\) from the second (\(b_{1}=-a_{1}b_{0}/a_{0}\)), and so on.