ot: there's a really nice derivation in the first couple chapters of generatingfunctionology[0].

[0]: https://www.math.upenn.edu/~wilf/DownldGF.html