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:
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