Prove that 2^n + 1 is divisible by 3 for all positive odd integers n

Given

2n + 1 is divisible by 3 ∀ n ∈ O+

Proof

We will prove the given statement by induction.

STEP 1

n = 1

2n + 1 = 21 + 1 = 3

3 is divisible by 3. Therefore, the statement is true for n = 1

STEP 2

Let the given statement be true for n = k

2k + 1 = 3x

Now, we need to prove that if the statement is true for n = k then it is also true for n = k + 2

Note: We are going to prove the statement to be true for n = k + 2 and not for n = k + 1 because k is odd. Therefore, k + 1 is even. The next odd number after k is k + 2.

2k+2 + 1 = 2k*4 + 1

= ( 3x – 1 )*4 + 1

= 12x – 4 + 1

= 12x – 3

= 3 * ( 4x – 1 )

Thus, we can say that 2k+2 + 1 is divisible by 3 if 2k + 1 is divisible by 3.

Therefore, we can say that if the given statement is true for n = k, then it is also true for n = k + 2. Hence, by the principle of mathematical induction, the given statement is true ∀ n ∈ O+.

Leave a Comment

Your email address will not be published. Required fields are marked *