Generating Functions · Generating Functions

Lesson 8

Nikolai Chukhin · Alexander S. Kulikov

Consider the generating function of the sequence \((1,1,1,1,\dotsc)\): \[\mathcal{G}(x)=1+x+x^{2}+x^{3}+\dotsb\] As it often happens, much can be simplified here if we slightly manipulate the series.

From the resulting equation for \(\mathcal{G}(x)\), we conclude that \[\mathcal{G}(x)=\frac{1}{1-x}\ .\] In other words, for any \(n \in \mathbb{Z}_{\ge 0}\), it holds that \[[x^{n}]\frac{1}{1-x}=1 \ .\] Even this simplest example demonstrates another remarkable property of generating functions: the generating function of many interesting sequences is defined simply and allows for a compact representation of the sequence.