In order for a proof by mathematical induction to be valid, the basis statement must be tr...

In order for a proof by mathematical induction to be valid, the basis statement must be true for n = a and the argument of the inductive step must be correct for every integer k ≥ a. In Find the mistakes in the “proofs” by mathematical induction.

Exercise

 “Theorem:” For all integers n > 1,3n – 2 is even.

“Proof (by mathematical induction): Suppose the theorem is true for an integer k, where k ≥ 1. That is, suppose that 3k – 2 is even. We must show that 3k+1 –2 is even. But

Now 3k – 2 is even by inductive hypothesis and 3k • 2 is even by inspection. Hence the sum of the two quantities is even (by Theorem). It follows that 3k+1 – 2 is even, which is what we needed to show.”

Theorem

The sum of any two even integers is even.

Proof:

Suppose m and n are [particular but arbitrarily chosen] even integers. [We must show that m + n is even.] By definition of even, m = 2r and n = 2s for some integers r and s. Then

Let t = r + s. Note that t is an integer because it is a sum of integers. Hence

m + n = 2t where t is an integer.

It follows by definition of even that m + n is even. [This is what we needed to show.]