Write 9 as 1+8 and expand by the binomial theorem.
9n+1=(1+8)n+1
=n+1C0+n+1C1(8)+n+1C2(8)2+n+1C3(8)3+⋯+n+1Cn+1(8)n+1
Since n+1C0=1 and n+1C1=n+1, take 82 common from the third term onwards.
9n+1=1+8(n+1)+82[n+1C2+n+1C3(8)+⋯+n+1Cn+1(8)n−1]
Let k=n+1C2+n+1C3(8)+⋯+n+1Cn+1(8)n−1. Each n+1Cr is an integer and each power of 8 is an integer, so k is an integer. Since 82=64,
9n+1=1+8(n+1)+64k
Now subtract 8n+9 from both sides.
9n+1−8n−9=1+8n+8+64k−8n−9
=64k
So 9n+1−8n−9 is a multiple of 64. Hence it is divisible by 64 for every positive integer n.