# Proof By Induction

#### shen07

##### Member

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

#### Deveno

##### Well-known member
MHB Math Scholar
Here is a start:

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

#### chisigma

##### Well-known member

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

##### Well-known member
MHB Math Scholar
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

##### Well-known member
Nicely done, Denevo! #### Petrus

##### Well-known member

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

##### Well-known member
MHB Math Scholar
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

##### Well-known member
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$$

Last edited: