Here are the /Solutions.

# 1. High and mighty

An integer n is **high** if n >= 1 and, for any m < n, if m is high then n >= 2m.

An integer n is **mighty** if n >= 1 and n is strictly greater than the sum of all smaller mighty integers.

Show that an integer is high if and only if it is mighty.

# 2. Injections, surjections, and compositions

- Prove or disprove: f∘g is injective if and only if both f and g are injective.
- Prove or disprove: f∘g is surjective if and only if both f and g are surjective.

# 3. A big product

Just as

represents the sum f(a)+f(a+1)+...+f(b), the notation

represents the product f(a)*f(a+1)*...*f(b).^{1}

Give a simple formula for the value of

as a function of n, and prove that it works for all integers n >= 1.

# 4. A big sum

Give a simple formula for the value of

as a function of n, and prove that it works for all integers n >= 1.

# 5. A recurrence

Let T(n) = T(n/3) + n and let T(1) = 1. Give a simple formula for T(3^{k}) as a function of k, and prove that it works for all integers k >= 0.

*Clarification added 2005-09-18:* A formula that includes a summation symbol is not simple.

Or 1 if b < a; see SummationNotation. (1)