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

3^{n} − 2n − 1 is divisible by 4

#### Solution

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

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

**Step 1: **

For n = 1, 3^{n} − 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^{n} − 2n − 1 is divisible by 4, for all n ∈ N.