## Prove that for every positive integer n, 9^n – 8n -1 is divisible by 64.

Prove that for every positive integer , is divisible by 64.

This question screams proof by induction, so we start with the base case, which in this case is :

which is indeed divisible by 64.

Now, let’s assume that it holds true for some positive integer . ie:

for .

Now let’s see how we can use this to prove that the statement holds true for . For we have:

where we have manipulated the expression to contain the left hand side of the inductive hypothesis. Thereby, plugging in the inductive hypothesis, we get:

but clearly is an integer, so this is divisible by 64 and thus the statement holds true for , thus it holds true for all positive integers …