# 1. At the ice cream store

The Baskin-Baskin ice cream store has the unusual slogan "exactly 4^{n} 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^{n} 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^{n} }. 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

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

Plugging this back in to the F sum gives

This gives the suspiciously pleasant solution

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

## 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:

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^{4} + 3⋅2^{5})/(-1)^{2} = 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

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

Taking the product gives

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)^{2}. But more likely we have to expand it out using, say, the Binomial Theorem to get the coefficients of (1-z)^{3} and (1-z)^{2}. 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.