Given a sequence:

Let:

(this is called the exponential generating function of the sequence)

Note that is the exponential generating function of (try differentiating)

So if we have the recurrence equation: we must have:

Suppose there are two different solutions to this equation: (1) (maybe complex)

Then the general solution to this differential equation is: (for some constants A and B that depend on the initial conditions) where and are the roots of the equation (1)

Therefore:

Thus:

And we finally get (because of the uniqueness of the power series expansion of a function)

Read here to find out more about this topic: http://www.mathhelpforum.com/math-he...tionology.html