Massachusetts Institute of Technology Handout 4 Mathematics for Computer Science August 1, 2005 Professor Charles E. Leiserson

Induction Proofs: Valid or Invalid?

Determine whether the following proofs are valid. If a proof is wrong, pinpoint the precise error. If it is correct, justify each step.

Problem 1.

Claim: For all real x ≠ 0 and all natural numbers n, we have x^{n} = 1.

Proof. The proof is by strong induction on n with the hypothesis that x^{n} = 1 for all real x ≠ 0. For the base case, observe that if x ≠ 0, we have x^{0} = 1 by definition.

In the inductive step, assume that x^{0} = … = x^{n} = 1, and we shall prove that that x^{n+1} = 1. We reason as follows:

x^{n+1} = \frac{x^{n} · x^{n}}{x^{n−1}}
= \frac{1 · 1}{1}
= 1

Problem 2.

Claim: All the horses are the same color.

Proof. We shall prove that in every finite, nonempty set of horses, all are the same color. Since the set of all horses is finite, the claim follows.

The proof is by induction. The induction hypothesis that in every set of n horses, all are the same color. For the base case, note that in every set containing a single horse, all are the same color trivially. Now, assume that the induction hypothesis holds for every set of n ≥ 1 horses in order to prove that it holds for every set of n + 1 horses. Consider an arbitrary set of n + 1 horses, h_{1}, h_{2}, …, h_{n+1}. By induction, h_{1}, h_{2}, …, h_{n} are all the same color. Similarly, h_{2}, …, h_{n+1} are all the same color. Therefore, horse h_{1} is the same color as horses h_{2}, …, h_{n}, which are the same color as horse h_{n+1}. It follows that in every set of n + 1 horses, all are the same color.

Problem 3.

Claim: The sum 1 + 2 + ⋯ + n is at most some positive constant times n. Proof. The proof is by induction on n with the claim as the hypothesis. If n = 1, then the sum evaluates to 1, which is at most cn, where c is any constant greater than or equal to 1.

For the induction step, assume that the statement is true for n, that is, that

1 + 2 + ⋯ + n ≤ cn

for some positive constant c. Adding n + 1 to both sides, we obtain

1 + 2 + ⋯ + n + (n + 1) ≤ cn + (n + 1)
≤ (c + 1)(n + 1).

Since c is a positive constant, so is c+1. Therefore, the sum is at most some positive constant times n + 1 as claimed.