Generating Functions · Generating Functions

Lesson 10

Nikolai Chukhin · Alexander S. Kulikov

Let \[\mathcal{N}(x)=1+2x+3x^{2}+4x^{3}+\dotsb=\sum_{n=0}^{\infty}(n+1)x^{n} \ .\] Then

Thus, \[\mathcal{N}(x)=\frac{\mathcal{G}(x)}{1-x}=\frac{1}{(1-x)^2}\ .\] Hence, \[[x^{n}]\left(\frac{1}{(1-x)^2}\right) = n + 1 \ .\] This provides a compact representation of the sequence \((1,2,3,\dotsc)\).

This equality can be given a physical interpretation: \(a_{n}=n+1\) is the number of ways to choose \(n\) candies when two types of candies are available (say, chocolate and caramel). What is the generating function of the sequence \(\{a_{n}\}\)? If there were only one type of candy, it would be \(1+x+x^{2}+\dotsb=\frac{1}{1-x}\): there is one way to choose no chocolate candies, one way to choose one chocolate candy, one way to choose two chocolate candies, and so on. The generating function for two types is simply the product of the generating functions!