[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. A big product

Prove that, for all integers n greater than 1,

\[\prod_{i=2}^{n} \left(1 - \frac{1}{i}\right) = \frac{1}{n}.\]

1.1. Solution

We'll show it by induction on n for all n ≥ 1. For n = 1, we have

\[\prod_{i=2}^{1} \left(1 - \frac{1}{i}\right) = 1 = 1/n.\]

(from the definition of an empty product).

For larger n, compute

\prod_{i=2}^{n} \left(1 - \frac{1}{i}\right) 
&=& \left(1-\frac{1}{n}\right) \prod_{i=2}^{n-1} \left(1 - \frac{1}{i}\right) \\
&=& \left(1-\frac{1}{n}\right) \left(\frac{1}{n-1}\right) \\
&=& \left(\frac{n-1}{n}\right) \left(\frac{1}{n-1}\right) \\
&=& \frac{1}{n}.

2. A feudal tax system

Every day, a peasant earns 1 copper farthing. His landlord comes to him at the end of the day and taxes him for exactly 1/4 of his total wealth (including any money left over from previous days). Assuming that the two start with nothing and that neither person has any other source of income or expenditures, how much much does the landlord have after n days?

2.1. Solution

It's easiest to set up a recurrence for the peasant's wealth:

If we expand this out a few times we get

and we might reasonably guess that the correct formula is

P(n) = \sum_{i=1}^{x} (3/4)^i = (3/4) \frac{1-(3/4)^{x}}{1-3/4} = 3(1-(3/4)^{x})

for some value x (if we were writing this up really formally, we would figure out x first as below and then pretend we knew the right value all along, but let's see how we figure out x).

For P(0) = 0 we need (3/4)x = 1 or x = 0.

For P(1) = 3/4, we need (3/4)x = 3/4 or x = 1. So let's guess x = n, giving

P(n) = 3(1-(3/4)n) = 3 - 3(3/4)n.

To prove that this works, we proceed by induction using the recurrence relation:

P(0) = 0 = 3(1-(3/4)0). (Base case).

P(n) = (3/4)(1+P(n-1)) = (3/4)(1 + 3 - 3(3/4)n-1)) = 3 - 3(3/4)n.

This characterizes the peasant's wealth, but what we wanted was the landlord's wealth. Here we observe that the total wealth P(n) + L(n) of both peasant and landlord after n days is exactly n copper farthings, so if the peasant has 3 - (3/4)n farthings, the landlord must have n - 3 + 3(3/4)n farthings.

3. A counting game

Two small children are playing the game "I know a bigger number." The first player must name a natural number less than or equal to n, where n happens to be the largest number known to either child. Then the second player must name a larger number that is still less than or equal to n. The players continue to alternate with larger and larger numbers until one of them names n, at which point the game ends.

Given n, exactly how many different sequences of moves could the two children play?

3.1. Solution

The trick for this one is to notice that each game can be described by giving a sequence of increasing numbers ending in n. Any subset of the numbers less than n can appear in the sequence; there are exactly 2n such subsets, giving exactly 2n possible plays of the game.

4. Sets of functions

Given sets A and B, let AB be the set of all functions f:B→A.

  1. Prove or disprove: |∅B| = 0 for any set B.

  2. Prove or disprove: |1B| = 1 for any set B, where 1 = {∅}.

  3. Prove or disprove: If A has at least two elements, then there exists an injection from B to AB.

4.1. Solution

  1. Disproof: Let B = ∅. Then there is exactly one function from B to A (the empty function).
  2. Proof: Let f:B→1. Since 1 has only one element ∅, we have f(x) = ∅ for all x in B. Since this is true for any f, we have f = f' for any functions f, f' in 1B, and it follows that there is at most one function in 1B. But the function f given by { (x,∅) | x∈B } shows that there is at least one f in 1B, so we have exactly one such function.

  3. Proof: We'll show existence by the simple expedient of defining an injection f. Let x and y be distinct elements of A. For each b in B, define fb to be the function given by fb(b') = x if b = b' and fb(b') = y if b ≠ b'. We will now show that f is an injection. Suppose for some b, c in B we have fb = fc. Then fc(b) = fb(b) = x. But fc(b) can equal x only if b = c. It follows that f is injective.

2014-06-17 11:57