Day 13: CM, Page xii

Day 13: The last page of the table of contents and the last page before the main part of the book. The second half of the book covers binomial coefficients, "special numbers", generating functions, discrete probability, and asymptotics. I also just realized that there are 100 pages of answers and 30 pages of bibliography, and 20 pages of index. I hope that 150 days isn't too boring.

We've already looked at binomial coefficients a little, and "special numbers" (Stirling Numbers and Fibonacci Numbers), but what are generating functions and asymptotics?

"In mathematics a generating function is a formal power series whose coefficients encode information about a sequence a_n that is indexed by the natural numbers" (wikipedia).

An ordinary generating function is defined by:

The summation produces a sequence like:


The coefficients on the power series are 1, 1, 1, 1.... So this is the generating function for the sequence containing all ones. The sum's equality to 1/(1-x) holds for x in (-1,1). Not all generating functions will converge or have closed forms and some generating functions (like the one above) will only have closed forms for a range of numbers. For 1/(1-x) and x > 1, the sum clearly does not converge and does not match the closed form. However, for x < 1, the sum does converge. You can see that the equality holds under these conditions by multiplying both sides of the equation by (1-x):


Where m is a number approaching infinity. As m approaches infinity for x > 1, x^m approaches a giant number, so the closed form does not hold for |x| > 1. We'll get to learn much more about generating functions in a few hundred days.