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
![\[\sum_{k=a}^{b} f(k)\]](/pinewiki/CS202/2005/Assignments/HW02?action=AttachFile&do=get&target=latex_be852eea5481fb5923380d88cd406de44511c560_p1.png "\[\sum_{k=a}^{b} f(k)\]")
represents the sum f(a)+f(a+1)+...+f(b), the notation
![\[\prod_{k=a}^{b} f(k)\]](/pinewiki/CS202/2005/Assignments/HW02?action=AttachFile&do=get&target=latex_d6e2482d545b2b12515d2ad7b95cb8425e2265bd_p1.png "\[\prod_{k=a}^{b} f(k)\]")
represents the product f(a)*f(a+1)*...*f(b).1
Give a simple formula for the value of
![\[\prod_{k=1}^{n} \left(1-\frac{1}{k+1}\right)\]](/pinewiki/CS202/2005/Assignments/HW02?action=AttachFile&do=get&target=latex_5de978522693def20b0c4f0dff01983aaf31eee5_p1.png "\[\prod_{k=1}^{n} \left(1-\frac{1}{k+1}\right)\]")
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
![\[\sum_{k=1}^{n} \frac{1}{k(k+1)}\]](/pinewiki/CS202/2005/Assignments/HW02?action=AttachFile&do=get&target=latex_00a8affc8c5ef14f89428e691d820082fd7c0b99_p1.png "\[\sum_{k=1}^{n} \frac{1}{k(k+1)}\]")
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.
Or 1 if b < a; see SummationNotation. (1)