Mathematics 242 – Principles of Analysis Problem Set 2 – Selected Solutions September 27, 2004

8.4e/ We must construct a bijective mapping f : (0, 1) → R. In order to get the whole real line as the image of a function on a finite interval, we expect the graph must have vertical asymptotes at both x = 0 and x = 1, say with lim_{x→0^{+}} f(x) = −∞ and lim_{x→1^{−}} f(x) = +∞. We recall from calculus that the tangent function has a graph with the right general shape. However tan(x) has successive vertical asymptotes at x = −π/2 and x = π/2. So we must shift and “squeeze” the graph horizontally to place the asymptotes at x = 0 and x = 1. The function f(x) = tan(πx − π/2) will work for this purpose. Note that x = 0 corresponds to −π/2 and x = 1 corresponds to −π/2. Since tan(x) is strictly increasing on the open interval (−π/2, π/2), it is injective. It is continuous and surjective onto R. (A full proof of this requires a result called the Intermediate Value Theorem that we will prove in a few weeks.) Hence our f is a bijection from (0, 1) to R.

8.11/ a) We must show that there is a bijection f : (0, 1) → (m, n). The linear function with f(0) = m and f(1) = n will work for this purpose, since both endpoints of both intervals are omitted. We obtain f(x) = (n − m)x + m. This is injective since

f(x) = f(x′) ⇒ (n − m)x + m = (n − m)x′ + m ⇒ (n − m)x = (n − m)x′ ⇒ x = x′.

The surjectivity can be proved directly here (without recourse to the Intermediate Value Theorem). Given any y ∈ (m, n), we can solve the equation y = (n − m)x + m for x: x = \frac{y−m}{n−m}. If m < y < n, we see 0 < x < 1.

b) Using part a, we have bijections f : (0, 1) → (m, n) and g : (0, 1) → (m′, n′). The function h = g ∘ f^{−1} maps (m, n) to (m′, n′). Moreover h is a bijection since f^{−1} and g are bijections.

10.15/ We assume that p(n) is a collection of statements, one for each n ∈ N, satisfying

1) p(1) is true, and

2) p(1) ∧ p(2) ∧ ⋯ ∧ p(k) ⇒ p(k + 1) for all k ≥ 1.

We claim that p(n) is true for all n ∈ N (the principle of strong induction). The proof is by contradiction. Let F = {n : p(n) is false}, so we assume F is nonempty. By the Well-Ordering Principle, F has a smallest element n_{0}. By assumption 1, n_{0} > 1. Hence n_{0} − 1 ∈ N, and 1, 2, …, n_{0} − 1 ∈ N \ F, so p(1), …, p(n_{0} − 1) are all true. Then assumption 2 shows that p(1) ∧ ⋯ ∧ p(n_{0} − 1) implies p(n_{0}) is also true. But this is a contradiction, since n_{0} ∈ F. Therefore F must be empty, and p(n) is true for all n ∈ N.

10.18 a) Finding a common denominator, we have

\binom{n}{r} + \binom{n}{r − 1} = \frac{n!}{r!(n − r)!} + \frac{n!}{(r − 1)!(n − r + 1)!}

= \frac{n!((n − r + 1) + r)}{r!(n − r + 1)!}

= \frac{n!(n + 1)}{r!(n − r + 1)!}

= \frac{(n + 1)!}{r!(n − r + 1)!}

= \binom{n + 1}{r}

b) We must prove that

(a + b)^{n} = ∑_{i=0} \binom{n}{i}a^{n−i}b^{i} = \binom{n}{0}a^{n} + \binom{n}{1}a^{n−1}b + ⋯ + \binom{n}{n}b^{n}

This proof will be by induction on n. The base case n = 1 is true since

(a + b)^{1} = a + b = \binom{1}{0}a + \binom{1}{1}b

Now we assume as our induction hypothesis that

(a + b)^{k} = \binom{k}{0}a^{k} + \binom{k}{1}a^{k−1}b + ⋯ + \binom{k}{k}b^{k}.

Now we consider (a + b)^{k+1} and use the induction hypothesis:

(a + b)^{k+1} = (a + b)(a + b)^{k}

= (a + b) (\binom{k}{0}a^{k} + \binom{k}{1}a^{k−1}b + ⋯ + \binom{k}{k}b^{k})

= \binom{k}{0}a^{k+1} + \binom{k}{1}a^{k}b + \binom{k}{2}a^{k−1}b^{2} + ⋯ + \binom{k}{k}ab^{k}

\binom{k}{0}a^{k}b + \binom{k}{1}a^{k−1}b^{2} + ⋯ + \binom{k}{k − 1}ab^{k} + \binom{k}{k}b^{k+1}

We collect like terms and use part a. Then since \binom{k}{0} = \binom{k+1}{0} = \binom{k}{k} = \binom{k+1}{k+1} = 1,

= \binom{k + 1}{0}a^{k+1} + \binom{k + 1}{1}a^{k}b + \binom{k + 1}{2}a^{k−1}b^{2} + ⋯ + \binom{k + 1}{k + 1}b^{k+1}