Prove that 4^n-3n-1 is divisible by 9

To Prove

4ⁿ – 3n – 1 is divisible by 9 ∀ n ∈ N

Proof

We will prove the given statement using mathematical induction.

Step 1

First, we will check if the given statement is true for n = 1.

4ⁿ – 3n – 1 = 4¹ – 3(1) – 1 = 4 – 3 – 1 = 0

The statement is true for n = 1 since 0 is divisible by 9.

Step 2

In this step, we will assume that the statement is true for n = k. This implies that 4^k – 3k – 1 is divisible by 9. We can say

4^k – 3k – 1 = 9x, ∀ x ∈ N ……(1)

Step 3

In this step, we will check if the statement is true for n = k + 1 given that it is true for n = k.

$\\*4^{k+1}-3(k+1)-1 = 4^k.4-3k-3-1\\*4^{k+1}-3(k+1)-1 = 4^k.4-3k-4\\*4^{k+1}-3(k+1)-1 = 4(4^k-1)-3k ......(2)$

Substituting equation (1) in (2)

$\\*4^{k+1}-3(k+1)-1 = 4(9x+3k)-3k\\*4^{k+1}-3(k+1)-1 = 36x+12k-3k\\*4^{k+1}-3(k+1)-1 = 36x+9k\\*4^{k+1}-3(k+1)-1 = 9(4x+k)$

9(4x+k) is divisible by 9. This implies that the given statement is true for n = k + 1 given that the statement is true for n = k. Therefore, by the principle of mathematical induction, the given statement “4ⁿ – 3n – 1 is divisible by 9″ is true for all n ∈ N.

Leave a Comment Cancel Reply