1
$\begingroup$

I have been trying to prove that $9^n-8n-1$ is divisible by $8$ for all $n$ integers greater than 1. My progress: Let $n = 2$. This gives us the expression equal to $64$ which is a factor of 8. Now assume it is true for $n=k$ . for $n = k+1$ :

$$ 9^{k+1} - 8(k+1) - 1$$ $$ = (8+1)^{k} \times (8+1) -8k - 8 -1 $$

I keep getting stuck on this part. Can someone please hint me how I can proceed by using INDUCTION only?

$\endgroup$
6
$\begingroup$

$9^{k+1} - 8(k+1) - 1 = 9(9^k - 8k - 1) + (64k + 8)$

See what to do now?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm not sure why you took out $9$ as a common factor and not $8$ $\endgroup$ – Aspiring Mathlete Oct 31 '14 at 14:53
  • 1
    $\begingroup$ We want to show that $9^k - 8k - 1$ being divisible by $8$--the inductive hypothesis--implies $9(9^k - 8k - 1) + (64k + 8)$ is divisible by $8$. Now, the inductive hypothesis implies that $9(9^k - 8k - 1)$ is divisible by $8$ and so therefore is $9(9^k - 8k - 1) + (64k + 8) = 9(9^k - 8k - 1) + 8(8k + 1)$. $\endgroup$ – Simon S Oct 31 '14 at 15:00
2
$\begingroup$

$9^{k+1}-8(k+1)-1=8\cdot9^k+9^k-8k-8-1=8(9^k-1)+9^k-8k-1$

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Assume $9^k -8k -1 $ is divisible of 8. Then $$9^{k+1}-8(k+1)-1\equiv 1^{k+1}-0(k+1)-1\equiv1-0-1\equiv 0\pmod 8$$ so $9^{k+1}-8(k+1)-1$ is divisible by 8.

What? We didn't use the induction hypothesis? No matter -- the conclusion is no less true for that.


Alternatively, without modular arithmetic: By the binomial theorem $$ 9^{k+1} = (1+8)^{k+1} = \binom{k+1}0 1^{k+1}8^0 + (\text{terms all involving factors of }8) = 1 + 8c$$ for some $c$. Therefore $$9^{k+1}-8(k+1)-1 = 1 + 8c - 8(k+1) - 1 = 8(c-k-1) $$ which is clearly divisible by $8$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

By the binomial theorem, $9^{n}=(8+1)^{n}=8^2a+\binom{n}{1}8+1=64a+8n+1$, hence the result.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Induction appears in the binomial theorem... $\endgroup$ – lhf Oct 31 '14 at 15:04
  • $\begingroup$ Why show the $\binom n18$ term separately? $\endgroup$ – hmakholm left over Monica Oct 31 '14 at 15:54
  • $\begingroup$ @HenningMakholm, that's what the binomial theorem gives, but perhaps it's too much. $\endgroup$ – lhf Oct 31 '14 at 16:06
0
$\begingroup$

It is enough to prove $9^n - 1$ is a multiple of 8. ($8n$ being a multiple of 8, subtracting this from $9^n-1$, we obtain a multiple of 8). Now, \begin{align*} (9^{n+1}-1) - (9^n-1) = 9^n(9-1) = 8\cdot 9^n \end{align*} and we are through.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.