Sometimes a recurrence relation involves factorials, or binomial coefficients. When this happens, it becomes difficult if not impossible to use ordinary generating functions to find an explicit formul...Sometimes a recurrence relation involves factorials, or binomial coefficients. When this happens, it becomes difficult if not impossible to use ordinary generating functions to find an explicit formula for the nth term of the sequence. In some cases, a different kind of generating function, the exponential generating function, may succeed where an ordinary generating function fails.
Thus ex+e−x=∞∑i=02x2i(2i)!, so that ∞∑i=0x2i(2i)!=ex+e−x2. A similar manipulation shows that \[ \sum...Thus ex+e−x=∞∑i=02x2i(2i)!, so that ∞∑i=0x2i(2i)!=ex+e−x2. A similar manipulation shows that ∞∑i=0x2i+1(2i+1)!=ex−e−x2. Thus, the generating function we seek is ex−e−x2ex+e−x2ex=14(ex−e−x)(ex+e−x)ex=14(e3x−e−x). Notice the similarity to Example 3.2.4.