Discrete Mathmatics Induction

Question

 A proof by mathematical induction is supposed to show that a given property is true for every integer greater than or equal to an initial value. In order for it to be valid, the property must be true for the initial value, and the argument in the inductive step must be correct for every integer greater than or equal to the initial value.

Consider the following statement.

For every integer n ≥ 1,

 3ⁿ − 2

 is even.

The following is a proposed proof by mathematical induction for the statement.

Since the property is true for n = 1,

 the basis step is true. Suppose the property is true for an integer k, where k ≥ 1.

 That is, suppose that 3^k − 2

is even. We must show that 3^{k + 1} − 2

 is even. Observe that

3k + 1 − 2	=	3k · 3 − 2 = 3k(1 + 2) − 2
=	(3k − 2) + 3k · 2.

Now 3^k − 2

 is even by inductive hypothesis, and 3^k · 2

 is even by inspection. Hence the sum of the two quantities is even by (Theorem 4.1.1). It follows that 3^{k + 1} − 2

 is even, which is what we needed to show.

identify the error(s) in the proof. (Select all that apply.)

3^k − 2 is odd by the inductive hypothesis.

The inductive hypothesis is assumed to be true.

3^{k + 1} − 2 ≠ (3^k − 2) + 3^k · 2

The property is not true for n = 1.

The property is not true for n = 1.(3^k − 2) + 3^k · 2 ≠ 3^k(1 + 2) − 2

Answer 1

Proof by mathematical induction shows that

a statement is true FOR EVERY POSITIVE INTEGER.

The statement must be shown to hold true for

positive integer n=1,2 and optionally more

consecutive positive integers after that

so that the pattern is clearly exploited.

The statement then builds to the general

case which is that it is GIVEN that the

statement holds for some positive integer N.

This is the induction hypothesis.

Finally, to goal is to PROVE the statement

holds true for N+1.

All of this together completes the induction proof

because the statement holds true for N=1,2 at least.

Therefore, it must hold for N=3,4,....,N+1

==========================================

The statement is 3^n-1 is even for positive integer N.

N=1 --> 3^1-1 = 3-1=2 is even

N=2 --> 3^2-1 = 9-1=8 is even

N=3 ---> 3^3-1 = 27-1 = 26 is even

Induction hypothesis:

GIVEN that 3^n-1 is even for some positive integer N.

[PROVE: 3^(n+1)-1 is even]

3^(n+1) - 1 = 3^n * 3 - 1 <--- property of exponents

= 3^n *3 - 1 + 3 - 3 <--- adds 0 = 3-3

= 3^n*3 - 3 + 3-1 <--- commuatative

= (3^n*3 - 3) + (3-1) <--- associative

= 3( 3^n-1) + 2 <-- factors out 3

3^n-1 is even by given induction hypothesis.

So 3^n-1 = 2T for some integer T by definition.

= 3* (2T) + 2 <-- substitution

= 2 ( 3T+1) <--- factors out the 2.

By closure property of integer multiplication and addition,

3T+1 is an integer, which makes the original expression

divisibile by 2, or even

[end of proof]