Posted by: yanzhang | July 24, 2008

A Little Generating Function

Today, for unrelated reasons, elementary enumerative combinatorics came up twice at work, once from my boss and once from Alex Levin.

Problem:

Find the generating function for F(n, x) = \sum_{i \geq n} {i \choose n} x^{i-n}.

Proof:

Recognize that the coefficient for x^i is the number of ways to sum (n+1) nonnegative numbers to get i (using the standard “stars and bars” argument. Thus, the generating function must be the (n+1)_{th} power of the generating function which has coefficient 1 for each nonnegative integer, so our final function is \frac{1}{(1-x)^{n+1}}.

Especially when the generating function is not provided, coming up with this proof might be difficult. To keep with the theme of these posts, it is more instructive to give a “dirty” proof where I struggle and find the answer in a more motivated fashion, in case I had to solve this problem with a gun to my head.

Proof 2 and analysis:

From a good angle and impeccable timing, disarm the gun with ninja tactics. If that is not an option, the biggest metaprinciple in combinatorics problems is to do small cases (this seems more true for combinatorics than for the rest of math, where small cases are frequently either too sparse and become unmanageable very quickly and/or too trivial to give enough information). Note that the n=0 case happily gives \frac{1}{1-x}. No, this is probably not enough to guess the answer unless you know it already, so we save it as a base case.

The second tech is “how do I abuse the coefficients to make them talk?” The attack here is to look at how the objects are defined and find a way to relate the object to slightly augmented versions of itself and/or other things you already know. Hopefully, that would make more sense after I do the following.

So what are binomical coeffcients? At their most basic level, they are defined by base cases and {n+1 \choose i+1} = {n \choose i} + {n \choose i+1}. Hey – this caters to writing something as the sum of slightly “perturbed” versions of the same object, so we are on the right track. We now want to write out the coefficient of F(n,x) and try to line it up with a slightly different generating function so we end up using the above identity. It shouldn’t take long to see that if we shift the function by x and subtract from itself, we (almost) get the function for (n-1): (F(n, x) - 1)/x - F(n, x) = (F(n-1, x) - 1) / x, which reduces to (1-x) F(n, x) = F(n-1, x). Given our base case, we are clearly done.

I think this is called the “inverse binomial coefficient generating function.” Don’t quote me on it.

-Y

Source: Alex Levin

P.S. “Frequently, we prove the same theorem twice – once to show ourselves, once to show others.” – H. Nagy

P.S.S. I definitely came up with the second proof first.

Advertisements

Responses

  1. Sorry, I don’t know how to TeX in WordPress and you don’t have a preview feature (hint hint).

    By the binomial theorem, (i choose n) * x^(i-n) is the coefficient of y^n in the expansion of (x+y)^i. If we sum over all i, we get sum (x+y)^i = (1-x-y)^-1.

    Finally, we just have to determine the coefficient of y^n. But that’s just 1/n! * d^n/dy^n of that, evaluated at y=0. The normalized derivative is (1-x-y)^(-n-1), and so finally we get (1-x)^(-n-1).

  2. that’s hot, B.

    For future ref, to latex statement A, just put $’s around your statement, though you need to put the word “latex” right after the first $.

  3. I still wish there were a preview feature, but apparently WordPress makes that difficult. For practice, here’s my comment TeXed: (i.e., let’s see if I screwed up!)

    By the binomial theorem, \binom{i}{n} x^{i-n} is the coefficient of y^n in the expansion of (x+y)^i. If we sum over all i, we get \sum_i (x+y)^i = (1-x-y)^{-1}.

    Finally, we just have to determine the coefficient of y^n. But that’s just \frac{1}{n!} \cdot \frac{d^n/dy^n} of that, evaluated at y=0. The normalized derivative is (1-x-y)^{-n-1}, and so finally we get (1-x)^{-n-1}.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: