4.2: More on Induction

In the previous section, we discussed proving statements of the form \((\forall n \in \mathbb{N}) P(n)\). Mathematical induction can actually be used to prove a broader family of results; namely, those of the form

\((\forall n \in \mathbb{Z})(n \geq a \implies P(n))\)

for any value \(a \in \mathbb{Z}\). Theorem 4.2 handles the special case when \(a = 1\). The ladder analogy from the previous section holds for this more general situation, too. To prove the next theorem, mimic the proof of Theorem 4.2, but this time use the set \(S=\{k\in \mathbb{N}\mid P(a+k-1) \text{ is true}\}\).

Theorem 4.9. Let \(P(a), P(a+1), P(a+2), \ldots\) be a sequence of statements, one for each integer greater than or equal to \(a\). Assume that

1. \(P(a)\) is true, and
2. if \(P(k)\) is true, then \(P(k+1)\) is true.

Then \(P(n)\) is true for all integers \(n \geq a\).

Theorem 4.9 gives a process for proving statements of the form: “For all integers \(n\geq a\), \(P(n)\).” As before, hypothesis (i) is called the base step, and (ii) is called the inductive step.

Skeleton Proof 4.10. Here is the general structure for a proof by induction when the base case does not necessarily involve \(a=1\).

We proceed by induction.

1. Base step: [Verify that \(P(a)\) is true. This often, but not always, amounts to plugging \(n=a\) into two sides of some claimed equation and that both sides are actually equal.]
2. Inductive step: [Your goal is to prove “For all \(k\in\mathbb{Z}\), if \(P(k)\) is true, then \(P(k+1)\) is true.”] Let \(k \ge a\) be an integer and assume that \(P(k)\) is true. [Do something to derive that \(P(k+1)\) is true.] Therefore, \(P(k+1)\) is true.

Thus, by induction, \(P(n)\) is true for all integers \(n \ge a\).

We encountered the next theorem back in Section 3.3 (see Conjecture 3.29), but we did not prove it. When proving this theorem using induction, you will need to argue that if you add one more element to a finite set, then you end up with twice as many subsets. For your base case, consider the empty set.

Theorem 4.11. If \(A\) is a finite set with \(n\) elements, then \(\mathcal{P}(A)\) is a set with \(2^{n}\) elements.

Theorem 4.12. For all integers \(n \ge 0\), \(n<2^n\).

One consequence of the previous two theorems is that the power set of a finite set always consists of more elements than the original set.

Theorem 4.13. For all integers \(n \ge 0\), \(4\) divides \(9^n - 5\).

Theorem 4.14. For all integers \(n \ge 0\), \(4\) divides \(6\cdot 7^n - 2 \cdot 3^n\).

Theorem 4.15. For all integers \(n \ge 2\), \(2^n > n + 1\).

Theorem 4.16. For all integers \(n \ge 0\), \(1 + 2^1 + 2^2 + \cdots + 2^n = 2^{n+1} - 1\).

Theorem 4.17. Fix a real number \(r \neq 1\). For all integers \(n \ge 0\), \[\displaystyle{1 + r^1 + r^2 + \cdots + r^n = \frac{r^{n+1} - 1}{r-1}}.\]

Theorem 4.18. For all integers \(n \ge 3\), \(\displaystyle{2\cdot 3 + 3 \cdot 4 + \cdots + (n-1)\cdot n = \frac{(n-2)(n^2+2n+3)}{3}}\).

Theorem 4.19. For all integers \(n \ge 1\), \(\displaystyle{\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \cdots + \frac{1}{n(n+1)} = \frac{n}{n+1}}\).

Theorem 4.20. For all integers \(n \ge 1\), \(\displaystyle{\frac{1}{1\cdot 3} + \frac{1}{3\cdot 5} + \frac{1}{5\cdot7} + \cdots + \frac{1}{(2n-1)(2n+1)} = \frac{n}{2n+1}}\).

Theorem 4.21. For all integers \(n \ge 0\), \(3^{2n}-1\) is divisible by \(8\).

Theorem 4.22. For all integers \(n \ge 2\), \(2^n < (n+1)!\).

Theorem 4.23. For all integers \(n \ge 2\), \(2\cdot 9^n - 10 \cdot 3^n\) is divisible by \(4\).

We now consider an induction problem of a different sort, where you have to begin with some experimentation. For Part (c), consider using the results from Parts (a) and (b).

Problem 4.24. Suppose \(n\) lines are drawn in the plane so that no two lines are parallel and no three lines intersect at any one point. Such a collection of lines is said to be in general position. Every collection of lines in general position divides the plane into disjoint regions, some of which are polygons with finite area (bounded regions) and some of which are not (unbounded regions).

1. Let \(R(n)\) be the number of regions the plane is divided into by \(n\) lines in general position. Conjecture a formula for \(R(n)\) and prove that your conjecture is correct.
2. Let \(U(n)\) be the number of unbounded regions the plane is divided into by \(n\) lines in general position. Conjecture a formula for \(U(n)\) and prove that your conjecture is correct.
3. Let \(B(n)\) be the number of bounded regions the plane is divided into by \(n\) lines in general position. Conjecture a formula for \(B(n)\) and prove that your conjecture is correct.
4. Suppose we color each of the regions (bounded and unbounded) so that no two adjacent regions (i.e., share a common edge) have the same color. What is the fewest colors we could use to accomplish this? Prove your assertion.