Show that 9n+1 – 8n – 9 is divisible by 64, whenever n is a positive integer.

In order to show that 9ⁿ⁺¹ – 8n – 9 is divisible by 64, it has to be show that 9ⁿ⁺¹ – 8n – 9 = 64 k, where k is some natural number

Using binomial theorem,

(1 + a)^m = ^mC₀ + ^mC₁ a + ^mC₂ a² + …. + ^m C _m a^m

For a = 8 and m = n + 1 we get

(1 + 8)ⁿ⁺¹ = ⁿ⁺¹C₀ + ⁿ⁺¹C₁ (8) + ⁿ⁺¹C₂ (8)² + …. + ⁿ⁺¹ C _n+1 (8)ⁿ⁺¹

9ⁿ⁺¹ = 1 + (n + 1) 8 + 8² [ⁿ⁺¹C₂ + ⁿ⁺¹C₃ (8) + …. + ⁿ⁺¹ C _n+1 (8)^n-1]

9ⁿ⁺¹ = 9 + 8n + 64 [ⁿ⁺¹C₂ + ⁿ⁺¹C₃ (8) + …. + ⁿ⁺¹ C _n+1 (8)^n-1]

9ⁿ⁺¹ – 8n – 9 = 64 k

Where k = [ⁿ⁺¹C₂ + ⁿ⁺¹C₃ (8) + …. + ⁿ⁺¹ C _n+1 (8)^n-1] is a natural number

Thus, 9ⁿ⁺¹ – 8n – 9 is divisible by 64, whenever n is positive integer.

Hence the proof