Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Generating functions are formed by making a series $\sum_{n\geq 0} a_n x^n$ out of a sequence $a_n$. They are used to count objects in enumerative combinatorics.

A generating function is a formal power series of the form \begin{equation*} f(x)=\sum^{\infty}_{n=0}a_nx^n \end{equation*} whose coefficients contain information about $a_n$, the sequence of numbers. For instance, suppose that the sequence is the Fibonacci sequence $0,1,1,2,3,5,8,\ldots$ Then$$f(x)=x+x^2+2x^3+3x^4+5x^5+\cdots,$$$$xf(x)=x^2+x^3+2x^4+3x^5+\cdots,$$and$$x^2f(x)=x^3+x^4+2x^5+\cdots.$$Then, it follows from the definition of the Fibonacci sequence that$$(1-x-x^2)f(x)=x$$This fact can be used to prove properties of the sequence, such as that its $n^\text{th}$ term is$$F_n = \frac{\varphi^n-(-\varphi)^{-n}}{\sqrt5},$$where $\varphi$ is the golden ratio.

history | excerpt history