[FrontPage] [TitleIndex] [WordIndex

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 4n 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 4n 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.

2. A tricky sum

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

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

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.)

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.

2014-06-17 11:57