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.

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

1. Prove or disprove: f∘g is injective if and only if both f and g are injective.
2. 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(3k) 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.

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

2014-06-17 11:57