Question

Prove by method of induction, for all n ∈ N:

3ⁿ − 2n − 1 is divisible by 4

Answer 1

3ⁿ − 2n − 1 is divisible by 4 if and only if 3ⁿ − 2n − 1 is a multiple of 4.

Let P(n) ≡ 3ⁿ − 2n − 1 = 4m, where m ∈ N.

Step 1:

For n = 1, 3ⁿ − 2n − 1 = 3 − 2 − 1 = 0

which is divisible by 4.

∴ P(1) is true.

Step 2:

Let us assume that for some k ∈ N, P(k) is true,

i.e., 3^k − 2k − 1 = 4a, where a ∈ N

∴ 3^k = 4a + 2k + 1   ...(1)

Step 3:

To prove that P(k + 1) is true, i.e., to prove that

3^k+1 − 2(k + 1) − 1 is a multiple of 4,

i.e., 3^k+1 − 2(k + 1) − 1 = 4b, where b ∈ N

Now, 3^k+1 − 2(k + 1) − 1 = 3^k.3 − 2k − 2 − 1

= (4a + 2k + 1)3 − 2k − 3  ..[By (1)]

= 12a + 6k + 3 − 2k − 3

= 12a + 4k

= 4(3a + k)

= 4b, where b = (3a + k) ∈ N

∴ P(k + 1) is true.

Step 4:

From all the above steps and by the principle of mathematical induction, P(n) is true for all n ∈ N,

i.e., 3ⁿ − 2n − 1 is divisible by 4, for all n ∈ N.