1

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?

Martin Sleziak
  • 53,687
Aspiring Mathlete
  • 2,312
  • 1
    Totally similar to http://math.stackexchange.com/questions/996049/proof-by-induction-that-16-mid-5n-4n-1, http://math.stackexchange.com/questions/966625/prove-by-induction-64-mid-72n-16n-−-1, and others. My rant about these still stands... – lhf Oct 31 '14 at 15:05
  • 1
    just do it directly: $8|8n$ and $8|9^n-1$. – Morris Oct 31 '14 at 15:14

5 Answers5

6

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

See what to do now?

Simon S
  • 26,524
  • I'm not sure why you took out $9$ as a common factor and not $8$ – Aspiring Mathlete Oct 31 '14 at 14:53
  • 1
    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)$. – Simon S Oct 31 '14 at 15:00
2

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

Przemysław Scherwentke
  • 13,668
  • 5
  • 35
  • 56
2

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$.

hmakholm left over Monica
  • 286,031
1

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

lhf
  • 216,483
0

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.