1
$\begingroup$

So I'm trying to use mathematical induction to show that for all integers $n \ge 1$ ,

$$ 8|(3^{2n} - 1)$$

(is divisible by 8)

I have my base case: [P(1)], $3^2 - 1 = 9 - 1 = 8$, since $8|8$, the base case proves true

Assume [P(k)], $ 8 | (3^{2k} - 1)$.

I know that I need to show [P(k+1)], $ 8| (3^{2(k+1)}-1) $, but I'm not sure how to prove this. I've only been using induction for summation, so how could I prove divisibility?

$\endgroup$
  • $\begingroup$ Try factoring out $3^2=8+1$. $\endgroup$ – Matt Samuel Nov 10 '14 at 1:51
  • $\begingroup$ Note also that $3^{2n}-1=(3^2)^n-1=9^n-1$. Now the claim follows from $a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+\cdots+b^{n-1})$. $\endgroup$ – Kim Jong Un Nov 10 '14 at 2:54
  • $\begingroup$ @Integrator it's correct though the identity in my comment is more elementary than the binomial theorem. $\endgroup$ – Kim Jong Un Nov 10 '14 at 8:03
1
$\begingroup$

If you don't mind I'm gonna do some magic $$3^{2n}=(3^2)^n=(8+1)^n=\binom{n}{o}8^n+\binom{n}{1}8^{n-1}+\cdots+\binom{n}{n-1}8^{1}+\binom{n}{n}8^0$$

$$3^{2n}=\binom{n}{0}8^n+\binom{n}{1}8^{n-1}+\cdots+\binom{n}{n-1}8^{1}+1$$

$$3^{2n}-1=\binom{n}{0}8^n+\binom{n}{1}8^{n-1}+\cdots+\binom{n}{n-1}8=8(k)$$

$$\implies8|(3^{2n} - 1)$$

$\endgroup$
3
$\begingroup$

Hint: Note that: $$3^{2(n+1)} -1=9\cdot3^{2n}-1=(3^{2n}-1)+8\cdot3^{2n}$$

$\endgroup$
  • $\begingroup$ How did you factor 9*3^(2n) -1 to equal (3^(2n) - 1)+ 8*3^(n)? (the last part) I don't understand how you were able to set them equal $\endgroup$ – Mark Nov 10 '14 at 2:03
  • 1
    $\begingroup$ $3^{2(n+1)} - 1 = 3^{2n+2} - 1 = 3^{2n}\cdot3^{2} - 1 = 9\cdot 3^{2n} - 1$ $ = (8+1)\cdot 3^{2n} - 1 = 8\cdot 3^{2n} + 1\cdot 3^{2n} - 1 = (3^{2n}-1) + 8\cdot 3^{2n}$ $\endgroup$ – JMoravitz Nov 10 '14 at 3:26
  • $\begingroup$ so i can make deduction that we assumed that 8|P(k) is true and so 8| 8*3^(2*n) so P(n) is true? $\endgroup$ – talmudist Oct 25 '15 at 19:01
  • $\begingroup$ @talmudist Assumed that $8|P(k)$ is true and show that $8| [P(k+1)=(3^{2k}-1)+8\cdot3^{2k}]=P(k)+8\cdot3^{2k}$ is true, then P(n) is true? $\endgroup$ – AsdrubalBeltran Oct 25 '15 at 21:43
  • $\begingroup$ from the question , yes $\endgroup$ – talmudist Oct 25 '15 at 22:00
1
$\begingroup$

Here is an alternative approach to that given by AsdrubalBeltran.

Write $3^{2n}-1$ is base three notations as :

$$3^{2n}-1 = \underbrace{22\dots2_{base 3}}_{2n \text{ times}}$$

Then since $ 8 = 22_3 $, we can see the result at once. Now use induction on n.

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