# Math Help - How to show this?

1. ## How to show this?

Show that $3^{2n} - 8n - 1$ is divisible by 64 for integer n > 1

2. Originally Posted by mark1950
Show that $3^{2n} - 8n - 1$ is divisible by 64 for integer n > 1
I suggest "proof by induction". If n= 2, we have $3^4- 16- 1= 81- 17= 64$ which is obviously divisible by 64.

Now, assume that, for some k, $3^{2k}- 8k- 1$ is divisible by 64. That is, that $3^{2k}- 8k- 1= 64m$ for some integer m. Now look at $3^{2(k+1)}- 8(k+1)-1= 9(3^{2k})- 8k -8- 1$ $= 3^{2k}- 8k- 1- 8+ 8(3^{2k})= 64m- 8+ 8(3^{2k})= 64m- 8(3^{2k}-1)$. Now that is obviously divisible by 8 but 64? You would have to prove that $3^{2k}- 1$ is divisible by 8. That is $9^k- 1$. Is 1 less than a power of 9 always divisible by 8? 9- 1= 8, 81- 1= 80= 8(10), 729- 1= 728= 8(91), ...

Hmmm, looks like another proof by induction! As above it works for n= 1. Suppose that $9^k- 1= 8j$ for some integers k and j. Then $9^{k+1}- 1= 9(9^k)- 1= 8(9^k)+ 9^k- 1= 8(9^k)+ 8j= 8(9^k+ j)$. Yes! That completes the proof!

3. Wow!

How did you get from
$
9(3^{2k})- 8k -8- 1
$

to
$
= 3^{2k}- 8k- 1- 8+ 8(3^{2k})
$
?

4. Hello, mark1950!

Another inductive proof . . .

Show that $3^{2n} - 8n - 1$ is divisible by 64 for integer $n > 1$
Verify $S(1)\!:\;\;3^2 - 8(1) - 1 \:=\:0$, which is divisible by 64.

Assume $S(k)\!:\;\;3^{2k} - 8k - 1 \:=\:64a\:\text{ for some integer }k.$

Add $8\cdot3^{2k} - 8$ to both sides:

. . . $3^{2k} {\color{blue}+ \:8\cdot 3^{2k}} - 8k\: {\color{red} -\: 8} - 1 \;=\;8a {\color{blue}\:+\: 8\cdot 3^{2k}} {\color{red}\:-\:8}$

. . $(8 + 1)\!\cdot\!3^{2k} - 8(k+1) - 1 \;=\;8a + 8\!\cdot\!3^{2k} - 8$

. . . . . . $9\!\cdot\!3^{2k} - 8(k+1) - 1 \;=\;8a + 8\!\cdot\!3^{2k} - 8$

. . . . . $3^2\!\cdot\!3^{2k} - 8(k+1) - 1 \;=\;8a + 8\!\cdot\!3^{2k} - 8$

. . . . . . $3^{2k+2} - 8(k+1) - 1 \;=\;8a + 8\!\cdot\!3^{2k} - 8$

. . . . . $3^{2(k+1)} - 8(k+1) - 1 \;=\;8\left(a + 3^{2k} - 1\right)\quad\leftarrow\:\text{ multiple of 8}$

We have proved $S(k+1)$.
. . The inductive proof is complete.

5. Originally Posted by mark1950
Show that $3^{2n} - 8n - 1$ is divisible by 64 for integer n > 1
Very Easy.

$9^n-8n-1=(1+8)^n-8n-1$

$
(1+8)^n=\binom{n}{0}+\binom{n}{1}8+\binom{n}{2}8^2 +\binom{n}{3}8^3+\binom{n}{4}8^4+........+\binom{n }{n}8^n
$

$
9^n=1+8n+8^2\left(\binom{n}{2}+\binom{n}{3}8+\bino m{n}{4}8^2+........+\binom{n}{n}8^{n-2}\right)
$

$
3^{2n}-8n-1=64\left(\binom{n}{2}+\binom{n}{3}8+\binom{n}{4}8 ^2+........+\binom{n}{n}8^{n-2}\right)
$

Q.E.D

6. Originally Posted by Soroban
Hello, mark1950!

Another inductive proof . . .

Verify $S(1)\!:\;\;3^2 - 8(1) - 1 \:=\:0$, which is divisible by 64.

Assume $S(k)\!:\;\;3^{2k} - 8k - 1 \:=\:64a\:\text{ for some integer }k.$

Add $8\cdot3^{2k} - 8$ to both sides:

. . . $3^{2k} {\color{blue}+ \:8\cdot 3^{2k}} - 8k\: {\color{red} -\: 8} - 1 \;=\;8a {\color{blue}\:+\: 8\cdot 3^{2k}} {\color{red}\:-\:8}$

. . $(8 + 1)\!\cdot\!3^{2k} - 8(k+1) - 1 \;=\;8a + 8\!\cdot\!3^{2k} - 8$

. . . . . . $9\!\cdot\!3^{2k} - 8(k+1) - 1 \;=\;8a + 8\!\cdot\!3^{2k} - 8$

. . . . . $3^2\!\cdot\!3^{2k} - 8(k+1) - 1 \;=\;8a + 8\!\cdot\!3^{2k} - 8$

. . . . . . $3^{2k+2} - 8(k+1) - 1 \;=\;8a + 8\!\cdot\!3^{2k} - 8$

. . . . . $3^{2(k+1)} - 8(k+1) - 1 \;=\;8\left(a + 3^{2k} - 1\right)\quad\leftarrow\:\text{ multiple of 8}$

We have proved $S(k+1)$.
. . The inductive proof is complete.

How did you get
$8\cdot3^{2k} - 8$?

7. Originally Posted by mark1950
Show that $3^{2n} - 8n - 1$ is divisible by 64 for integer n > 1
P(2) is true

Assume P(k) is true or 3 $^{2k}-8k-1=64R$

$\Rightarrow 3^{2k}=64R+8K+1$-------------------(1)

$P(k+1)=3^{2k+2}-8k-8-1$

$\Rightarrow P(k+1)=3^{2k}\cdot9-8k-9$

$\Rightarrow P(k+1)=9(64R+8k+1)-8k-9$ [From 1]

$\Rightarrow P(k+1)=64R\times9+72k+9-8k-9$

$\Rightarrow P(k+1)=64R\times9+64k$

$\Rightarrow P(k+1)=64(9R+k)=64a$

So $3^{2n} - 8n - 1$ is divisible by 64 for integer n > 1

8. Originally Posted by great_math
P(2) is true

Assume P(k) is true or 3 $^{2k}-8k-1=64R$

$\Rightarrow 3^{2k}=64R+8K+1$-------------------(1)

$P(k+1)=3^{2k+2}-8k-8-1$

$\Rightarrow P(k+1)=3^{2k}\cdot9-8k-9$

$\Rightarrow P(k+1)=9(64R+8k+1)-8k-9$ [From 1]

$\Rightarrow P(k+1)=64R\times9+72k+9-8k-9$

$\Rightarrow P(k+1)=64R\times9+64k$

$\Rightarrow P(k+1)=64(9R+k)=64a$

So $3^{2n} - 8n - 1$ is divisible by 64 for integer n > 1
Hmm. I understood everything except for the last part. How did u got 64a? How did 64(9R + k) becomes 64a?

9. Originally Posted by mark1950
Hmm. I understood everything except for the last part. How did u got 64a? How did 64(9R + k) becomes 64a?
$64\times(9R+k)=64a$ where $a=(9R+k)$

10. Hmm...but how does that show that $3^{2n} - 8n - 1$ is divisible by 64 for integer n > 1?

11. When great math wrote 64(9R + k) = 64a, I'm guessing that he/she's just saying that P(k + 1) simplifies to 64 times some number, which he/she decided to call a. That's all.

01

12. Originally Posted by yeongil
When great math wrote 64(9R + k) = 64a, I'm guessing that he/she's just saying that P(k + 1) simplifies to 64 times some number, which he/she decided to call a. That's all.

01
Yes thats right!

13. Oh...so when the answer has 64 in it after doing the mathematical induction it is safe to say that it is proven already, right?

14. Originally Posted by mark1950
Oh...so when the answer has 64 in it after doing the mathematical induction it is safe to say that it is proven already, right?