We have to prove that 9n+1 - 8n - 9 = 64k
∴ 9n+1 - 8n - 9 = (8+1)n+1 - 8n - 9 [put 9 = 8 + 1]
= [

n+1

‌

C8n+1+...+

n+1

‌

Cn−283 +

n+1

‌

Cn−182+

n+1

‌

Cn8+

n+1

‌

Cn+1] - 8n - 9
=

n+1

‌

C8n+1 + ... +

n+1

‌

Cn−283 +

n+1

‌

Cn−182 + (n + 1) 8 + 1 - 8n - 9
=

n+1

‌

C8n+1 + ... +

n+1

‌

Cn−283 +

n+1

‌

Cn−182
= 82 [

n+1

‌

C08n−1+...+

n+1

‌

Cn−28 +

n+1

‌

Cn−1]
= 64k [Where , k =

n+1

‌

C08n−1 + ... +

n+1

‌

Cn−1]
Hence, 9n+1 - 8n - 9 is divisible by 64, whenever n is a positive integer.