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. Solve a recurrence

Let T(n) be defined by the recurrence

T(0) = 1.
T(1) = 0.
T(2) = 7.
For n≥3, T(n) = 6 T(n-3) + 7 T(n-2).

Give a closed-form expression for T(n).

2. Triplets

Suppose you have a collection of objects of varying weights, and there are exactly ${n+5 \choose 5}$ ways to make a sequence of three of these objects with total weight n. How many objects are there with weight n?

3. Birthdays

Suppose that P and Q each have birthdays that are equally likely to be any of the 365 days of the year,¹ and that the two birthdays are independent. What is the probability that both birthdays occur on the same day of the week in a non-leap year?

We are conditioning on the event that neither of them is born on February 29th. (1)