The Essence of Generation Functions and Coefficient Extraction

Question

Given the roles generating functions and coefficient extraction play in solving recurrence relations, they are clearly analogous to the Laplace Transform and Inverse Laplace Transform. A hypothesis would then be that generating functions transform a problem from the time domain to the frequency domain, and coefficient extraction transforms a problem from the frequency domain to the time domain. However, the integrand of a Laplace Transform multiplies the input function by a decaying exponential, whereas the "inside" of a generating function multiplies the input function by a growing polynomial. The shift between exponential and polynomial is common when switching between ODEs and recurrence relations; the eigenvalues of the same characteristic polynomial go in the exponent for linear ODEs and in the base for linear recurrence relations, but this takes place without sign change. The shifting VS growing distinction between Laplace Transforms and generating functions remains unexpected. Thus a generating function behaves more like the Inverse Laplace Transform in this respect, leaving coefficient extraction to perhaps play the role of the Laplace Transform. What shifts in domain are taking place when generating functions and when coefficient extraction are applied?

Answer 1

What you call a "polynomial" is actually a discrete Laplace transform ( or a $z$ transform) if viewed correctly. Consider:

$\sum a_n x^n=\sum a_n e^{n\log x}$

define $\log x =s$ and you get a discrete Laplace transform

$\sum a_n x^n=\sum a_n e^{ns}$