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

1.1. Solution

Multiplying each equation by zⁿ and summing over all n gives the generating function equation

$\begin{align*} F = \sum_{n=0}^{\infty} T(n) z^n &= 1 + 7z^2 + \sum_{n=3}^{\infty} 6 T(n-3) z^n + \sum_{n=3}^{\infty} 7 T(n-2) z^n \\ &= 1 + 7 z^2 + \sum_{n=0}^{\infty} 6 T(n) z^{n+3} + \sum_{n=1}^{\infty} 7 T(n) z^{n+2} \\ &= 1 + \sum_{n=0}^{\infty} 6 T(n) z^{n+3} + \sum_{n=0}^{\infty} 7 T(n) z^{n+2} \\ &= 1 + 6z^3 F + 7 z^2 F. \end{align*}$

Solving for F gives

$\begin{align*} F &= \frac{1}{1-7z^2-6z^3} \\ &= \frac{1}{(1+z)(1+2z)(1-3z)} \\ &= \frac{A}{1+z} + \frac{B}{1+2z} + \frac{C}{1-3z}. \end{align*}$

The cover-up method gives A = 1/((1-2)(1+3)) = -1/4, B = 1/((1-1/2)(1+3/2)) = 4/5, and C = 1/((1+1/3)(1+2/3)) = 9/20. So we have

$\begin{align*} F &= \frac{-1/4}{1+z} + \frac{4/5}{1+2z} + \frac{9/20}{1-3z}. \end{align*}$

From this we can immediately read off the solution

$T(n) = \frac{9}{20} 3^n + \frac{4}{5} (-2)^n - \frac{1}{4} (-1)^n.$

The first few values of this function are given in the table below. It is not hard to check that these satisfy the recurrence.

n	T(n)
0	1
1	0
2	7
3	6
4	49
5	84
6	379

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?

2.1. Solution

Let a_n be the number of objects in S with weight n, and let F = ∑ a_nzⁿ be the generating function for these quantities. Then we have

$\begin{align*} F^3 &= \sum_{n=0}^{\infty} {n+5 \choose 5} z^n \\ &= \sum_{n=0}^{\infty} {n+5 \choose n} z^n \\ &= \sum_{n=0}^{\infty} {-6 \choose n} (-1)^n z^n \\ &= \sum_{n=0}^{\infty} {-6 \choose n} (-z)^n \\ &= (1-z)^{-6}. \end{align*}$

One solution to this equation is F = (1-z)^-2, which generates the sequence a_n = n+1. (The other solutions generate complex numbers for a_n—we don't want these.) So there are n+1 objects of weight n.

Check: Call the objects 0, 1a, 1b, 2a, 2b, 2c, etc. Then we get ${5 \choose 5} = 1$ triplet 000 of weight 0, ${6 \choose 5} = 6$) triplets 001a 01a0 1a00 001b 01b0 1b00 of weight 1, and <<latex(${7 \choose 5} = 21$ triplets of weight 2. The last are a pain to enumerate completely, but we can observe that there are 3*3=9 ways to build a triplet out of two 0's and a 2 (3 choices of where to put the 2 and 3 choices of 2's), plus another 3*2*2 ways to build a triplet out of one 0 and two 1's (3 choices of where to put the zero plus 2 choices each of the 1 labels). So this gives a total of 21.

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?

3.1. Solution

We can think of P and Q's birthdays as independent integer-valued random variables drawn uniformly from the range 1..365. We can determine the weekday of each birthday by computing P mod 7 and Q mod 7; the question then asks how likely it is that P mod 7 = Q mod 7. Note that this will not be exactly 1/7 because there is a slight variation in the number of values that produce each remainder.

Recalling that a year has approximately 52 weeks, we note that the first 52*7 = 364 days of the year produces exactly 52 of each weekday. The last day of the year gives one extra copy of some weekday. So

$\begin{align*} \Pr[P \bmod 7 = Q \bmod 7] &= \sum_{k=0}^{6} \Pr[P \bmod 7 = k \wedge Q \bmod 7 = k] \\ &= 6 \left(\frac{52}{365}\right)^2 + \left(\frac{53}{365}\right)^2 \\ &= \frac{19033}{133225}. \end{align*}$

This is an example of an answer where the second-to-last step may be more informative that the last one. Further calculation shows that the probability is greater than 1/7, but not by much.

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