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