Proof By Induction: Proving Divisibility of 3^2n-1 by 8

[shen07]

Hello Guys can you tell me how do i go about this question:

Question
Prove by Induction that for every positive integer n.
$$3^{2n} -1$$ is divisible by 8

 

[Deveno]

Here is a start:

$3^{2(n+1)} - 1 = 3^{2n+2} - 1 = (3^{2n} - 1)(3^2) + 3^2 - 1$

 

[chisigma]

Hello Guys can you tell me how do i go about this question:

Question
Prove by Induction that for every positive integer n.
$$3^{2n} -1$$ is divisible by 8

Remembering that...

$\displaystyle \sum_{k=0}^{n} x^{n}= \frac{x^{n+1}-1}{x-1} \implies x^{n+1}-1 = (x-1)\ \sum_{k=0}^{n} x^{n}\ (1)$

... and that...

$\displaystyle 3^{2 n +2}-1 = (3^{n+1}-1)\ (3^{n+1}+1)\ (2)$

... it is evident that the expression (2) contains both 3-1 and 3+1 so that is divisible by 8...

Kind regards

$\chi$ $\sigma$

 

[Deveno]

Remembering that...

$\displaystyle \sum_{k=0}^{n} x^{n}= \frac{x^{n+1}-1}{x-1} \implies x^{n+1}-1 = (x-1)\ \sum_{k=0}^{n} x^{n}\ (1)$

... and that...

$\displaystyle 3^{2 n +2}-1 = (3^{n+1}-1)\ (3^{n+1}+1)\ (2)$

... it is evident that the expression (2) contains both 3-1 and 3+1 so that is divisible by 8...

Kind regards

$\chi$ $\sigma$

That is a very good DIRECT proof, but does not use induction.

Another direct proof:

$3^{2n+2} - 1 = (3^2 - 1)(3^{2n} + 3^{2n - 2} + \cdots + 3^2 + 1)$

where it is evident that $3^2 - 1 = 8$ divides the RHS.

 

[DreamWeaver]

Nicely done, Denevo! (Clapping)

 

[Petrus]

Hello Guys can you tell me how do i go about this question:

Question
Prove by Induction that for every positive integer n.
$$3^{2n} -1$$ is divisible by 8

Just asume \(\displaystyle 3^{2n}-1\) is divided by 8
and for k+1
\(\displaystyle 3^{2(k+1)}-1\)
\(\displaystyle 3^{2k}•9-1\) and replace that -1 with +8-9
\(\displaystyle 3^{2k}•9-9+8\) factour out 9 from \(\displaystyle 3^{2k}•9-9\), can you finish?

Regards,
\(\displaystyle |\pi\rangle\)

 

[Deveno]

Just asume \(\displaystyle 3^{2n}-1\) is divided by 8
and for k+1
\(\displaystyle 3^{2(k+1)}-1\)
\(\displaystyle 3^{2k}•9-1\) and replace that -1 with +8-9
\(\displaystyle 3^{2k}•9-9+8\) factour out 9 from \(\displaystyle 3^{2k}•9-9\), can you finish?

Regards,
\(\displaystyle |\pi\rangle\)

Indeed, that is what I was hinting at with post #2, except I wrote "9" as "$3^2$" and "8" as "$3^2 - 1$" to make the inductive nature a bit more transparent.

(By the way, you can use the command \ast in latex to make an asterisk (star) for "multiply" instead of using a text bullet point. If you prefer a simple dot, the command \cdot (center dot) works well also).

 

[Petrus]

Indeed, that is what I was hinting at with post #2, except I wrote "9" as "$3^2$" and "8" as "$3^2 - 1$" to make the inductive nature a bit more transparent.

(By the way, you can use the command \ast in latex to make an asterisk (star) for "multiply" instead of using a text bullet point. If you prefer a simple dot, the command \cdot (center dot) works well also).

Hi Deveno,
Sorry for repositing your soultion.. I should read the comment first as I fast scroll I just saw inderect proof.. I Kinda for some reason like doing induction proof for this kind of problem, sorry I Will not repeat this again!

Thanks for latex tips! I had no clue about them but now I know and I Will now start to use them!
Edit: if you want here is how you do with modulo,
\(\displaystyle 3^{2n}=9^n\) and if we take modulo, let's say \(\displaystyle ;\) is that modulo sign as I forgot the latex code:/
\(\displaystyle 9^n;1^n\) (mod 8) and \(\displaystyle 1^n=1\)
and by showing modulo equal to zero it's mean it's divided
\(\displaystyle 3^{2n}-1;1-1=0\)
It's morning I Hope the fast show is enough:S for some reason I just starten to think about this problem-.-
Regards,
\(\displaystyle |\pi\rangle\)