For all integers n >= 1, which of the following is divisible by 9?

Question

For all integers n \(\geq\) 1, which of the following is divisible by 9?

(a) 8ⁿ + 1 

(b) 10ⁿ + 1 

(c) 4ⁿ – 3n + 1

 (d) 3²ⁿ + 3n + 1

Answer 1

Answer: (C) 4ⁿ-3n+1

For n = 1, 

8ⁿ + 1 = 8¹ + 1 = 9 divisible by 9 

10ⁿ + 1 = 10¹ + 1 = 11 not divisible by 9 

4ⁿ – 3n – 1 = 4 – 3 – 1 = 0 divisible by 9 

3²ⁿ + 3n + 1 = 13 not divisible by 9 

For n = 2

8ⁿ + 1 = 8² + 1 = 65 not divisible by 9 

4ⁿ – 3n – 1 = 4² – 3 × 2 – 1 = 16 – 6 – 1 = 9 divisible by 9 

∴ We need to prove 4n – 3n – 1 to be divisible by 9 ∀ n∈N. 

using mathematical induction. 

Let T(n): 4ⁿ – 3n – 1 is divisible by 9, 

Basic Step: 

T(1) = 0 which is divisible by 9 

⇒ T(1) is true. 

Induction Step: 

Assume T(k) to be true, i.e., 

4^k – 3k – 1 is divisible by 9 k∈N 

⇒ 4^k – 3k – 1 = 9m, m∈N ...(i) 

∴ 4^{k + 1} – 3(k + 1) – 1 = 4.4^k – 3k – 3 – 1 = 4.4^k – 3k – 4 

= 4(4^k – 3k – 1) + 9k = 4.9m + 9k = 9 (4m + k) 

⇒ 4^{k + 1} – 3 (k + 1) – 1 is divisible by 9 

⇒ T (k + 1) is true whenever T(k) is true, k∈N 

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