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 \[ e^x + e^{-x} = \sum_{i=0}^\infty {2x^{2i}\over (2i)!}, \nonumber\] so that \[ \sum_{i=0}^\infty {x^{2i}\over (2i)!} = {e^x+e^{-x}\over 2}. \nonumber\] A similar manipulation shows that \[ \sum...Thus \[ e^x + e^{-x} = \sum_{i=0}^\infty {2x^{2i}\over (2i)!}, \nonumber\] so that \[ \sum_{i=0}^\infty {x^{2i}\over (2i)!} = {e^x+e^{-x}\over 2}. \nonumber\] A similar manipulation shows that \[ \sum_{i=0}^\infty {x^{2i+1}\over (2i+1)!} = {e^x-e^{-x}\over 2}. \nonumber\] Thus, the generating function we seek is \[ {e^x-e^{-x}\over 2}{e^x+e^{-x}\over 2} e^x= {1\over 4}(e^x-e^{-x})(e^x+e^{-x})e^x = {1\over 4}(e^{3x}-e^{-x}). \nonumber\] Notice the similarity to Example 3.2.4.
