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+.