# 1. A big product

Prove that, for all integers n greater than 1,

## 1.1. Solution

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

(from the definition of an empty product).

For larger n, compute

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

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

If we expand this out a few times we get

- P(n) = 3/4 + (3/4)² + (3/4)³ + (3/4)⁴P(n-3)

and we might reasonably guess that the correct formula is

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 2^{n} such subsets, giving exactly 2^{n} possible plays of the game.

# 4. Sets of functions

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

Prove or disprove: |∅

^{B}| = 0 for any set B.Prove or disprove: |1

^{B}| = 1 for any set B, where 1 = {∅}.Prove or disprove: If A has at least two elements, then there exists an injection from B to A

^{B}.

## 4.1. Solution

- Disproof: Let B = ∅. Then there is exactly one function from B to A (the empty function).
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 1

^{B}, and it follows that there is at most one function in 1^{B}. But the function f given by { (x,∅) | x∈B } shows that there is at least one f in 1^{B}, so we have exactly one such function.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 f

_{b}to be the function given by f_{b}(b') = x if b = b' and f_{b}(b') = y if b ≠ b'. We will now show that f is an injection. Suppose for some b, c in B we have f_{b}= f_{c}. Then f_{c}(b) = f_{b}(b) = x. But f_{c}(b) can equal x only if b = c. It follows that f is injective.