Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

1. At the ice cream store

The Baskin-Baskin ice cream store has the unusual slogan "exactly 4ⁿ flavor combinations." By this they mean that if you are willing to spend n dollars for ice cream (plus a small fee for the cone), you can choose exactly 4ⁿ combinations of ice cream scoops on a two-scoop cone, where different orders are considered to be different combinations. This is a great improvement on the Robbins-Robbins store down the street, where they provide only vanilla scoops for $0 and chocolate scoops for $1, giving exactly one $0 cone (vanilla-vanilla), two $1 cones (vanilla-chocolate and chocolate-vanilla) and one $2 cone (chocolate-chocolate).

Deduce from Baskin-Baskin's slogan a closed-form expression for exactly how many different scoops of ice cream cost $n, for each value of n.

1.1. Solution

Let G = 1/(1-4z) be the generating function for the sequence { 4ⁿ }. We are looking for a sequence a_n whose generating function F satisfies F² = G. We can easily solve for F, obtaining F = 1/√(1-4z) = (1-4z)^-1/2. And now our troubles begin.

From the Binomial Theorem, we have

$F = (1-4z)^{-1/2} = \sum_{n=0}^{\infty} {-1/2 \choose n} (-4z)^n.$

Here the only tricky part is computing the binomial coefficient. Expand it as

$\begin{eqnarray*} {-1/2 \choose n} &=& \frac{(-1/2)_{(n)}}{n!} \\ &=& \frac{\prod_{i=0}^{n-1} (-1/2 - i)}{n!} \\ &=& \frac{\prod_{i=0}^{n-1} (2i + 1)}{(-2)^n n!} \\ &=& \frac{\left(\prod_{i=1}^{2n} i\right) / \left(\prod_{i=1}^{n} 2i\right)}{(-2)^n n!} \\ &=& \frac{(-1)^n}{2^{2n}} \cdot \frac{(2n)!}{n! \cdot n!} \\ &=& \frac{(-1)^n}{2^{2n}} { 2n \choose n }. \end{eqnarray*}$

Plugging this back in to the F sum gives

$\begin{eqnarray*} F &=& \sum_{n=0}^{\infty} {-1/2 \choose n} (-4z)^n \\ &=& \sum_{n=0}^{\infty} \frac{(-1)^n}{2^{2n}} { 2n \choose n } (-4z)^n \\ &=& \sum_{n=0}^{\infty} { 2n \choose n } z^n. \end{eqnarray*}$

This gives the suspiciously pleasant solution

$a_n = { 2n \choose n }.$

Some small values of this sequence are a₀ = 1, a₁ = 2, a₂ = 6, a₃ = 20, ... . It's not hard to check that we get 1⋅1=4⁰ $0 cones, (1⋅2)+(2⋅1) = 4¹ $1 cones, (1⋅6)+(2⋅2)+(6⋅1) = 4² $2 cones, and so forth.

2. A tricky sum

Find a closed-form expression in a and n for the value of

$\sum_{k=1}^n k a^k.$

2.1. Solution

This would be a standard geometric sum if it weren't for the extra k. So we need to pull down a copy of k from the exponent. Compute:

$\begin{eqnarray*} \sum_{k=0}^{n} a^k &=& \frac{1-a^{n+1}}{1-a}. \\ \sum_{k=1}^{n} k a^k &=& a \frac{d}{da} \sum_{k=0}^{n} a^k \\ &=& a \frac{d}{da} \frac{1-a^{n+1}}{1-a} \\ &=& a \left(\frac{1-a^{n+1}}{(1-a)^2} - \frac{(n+1)a^{n}}{1-a} \right)\\ &=& \frac{a-a^{n+2}}{(1-a)^2} - \frac{(n+1)a^{n+1}}{1-a} \\ &=& \frac{a-a^{n+2} - (n+1)a^{n+1} + (n+1)a^{n+2}}{(1-a)^2} \\ &=& \frac{a - (n+1)a^{n+1} + na^{n+2}}{(1-a)^2}. \end{eqnarray*}$

Quick test just to be safe: if a = 2, n = 3, we have 1⋅2 + 2⋅4 + 3⋅8 = 2 + 8 + 24 = 34. The formula gives (2 - 4⋅2⁴ + 3⋅2⁵)/(-1)² = 2 - 64 + 96 = 34. OK!

3. Counting change

Suppose you have an infinite collection of $1 bills (1), $1 coins (①) and $2 bills (2). Find a closed-form expression in n for the number of distinct ways to make $2n. (Example: for n=1, we get 4 ways to make $2: 11, 1①, ①①, and 2.)

3.1. Solution

This is an example of a problem that is probably easier to solve without generating functions. First we'll figure out how many ways there are to make $2n using just 1 and ①. Here we can choose anywhere from 0 to 2n 1's, giving 2n+1 possibilities.

If we are now allowed 2's, we have n+1 choices of how many 2's to use, leaving 0, 2, 4, ..., 2n dollars left to divide between 1's and ①'s. So the total number of ways to do this is

$\sum_{i=0}^{n} (2i+1) = 2\frac{n(n+1)}{2} + (n+1) = n(n+1) + (n+1) = (n+1)^2.$

If one must solve the problem using generating functions, the trick is to make one unit of weight equal $2. Then the generating function for $2 bills is just our old friend 1/(1-z) and the generating function for the $1 objects is

$\sum_n (2n+1) z^n = \frac{2z}{(1-z)^2} + \frac{1}{1-z}.$

Taking the product gives

$\frac{2z}{(1-z)^3} + \frac{1}{(1-z)^2}.$

If we are very lucky we might recognize this as d/dz (z d/dz 1/(1-z)) = d/dz (z/(1-z)²) = 2z/(1-z)³ + 1/(1-z)², the generating function for (n+1)². But more likely we have to expand it out using, say, the Binomial Theorem to get the coefficients of (1-z)³ and (1-z)². We leave this pleasant and enjoyable task as an exercise for the reader.

4. Independence

Let and A and B be independent events on some probability space. Prove or disprove: their complements -A and -B are also independent.

4.1. Solution

Let Pr[A] = p and Pr[B] = q. From independence of A and B we have Pr[AB] = pq. Since A is a disjoint union of A∩B and A∩-B, we have Pr[A] = Pr[AB] + Pr[A∩-B] so Pr[A∩-B] = p - pq. Similarly we have that -B is a disjoint union of -A∩-B and A∩-B; it follows that Pr[-B] = 1-q = Pr[-A∩-B] + Pr[A∩-B] and thus that Pr[-A∩-B] = 1-q-Pr[A∩-B] = 1-q-(p-pq) = 1-p-q+pq = (1-p)(1-q) = Pr[-A]Pr[-B]. But then we have Pr[-A∩-B] = Pr[-A]Pr[-B], so -A and -B are independent.