Proof formula with induction

Question

How can I prove by induction that $\forall n\in\mathbb{N}: \ 3^{2n} - 1$ is divisible by $8$.

Proof for $n=1$: $\displaystyle3^{2\cdot1} - 1 = 8$ which is divisible by $8$.

How can I prove it for $n+1$? this is where I got so far: $3^{2(n+1)} - 1 = 3^{2n+2} -1$

score 2 · Accepted Answer · answered Oct 16 '14 at 21:51

2

$3^{2n+2}-1=3^{2n}\cdot{3^2}-1=9\cdot{3^{2n}}-1=8\cdot{3^{2n}}+(3^{2n}-1)$

Proof with no induction: $3^{2n}-1=9^n-1^n=(9-1)(9^{n-1}+9^{n-2}+...+1)=8(9^{n-1}+9^{n-2}+...+1)$ which is of course divisible by 8.

answered Oct 16 '14 at 21:51

Galc127

4,451

The second proof actually uses induction. – egreg Oct 16 '14 at 22:25

score 2 · Answer 2 · edited Oct 16 '14 at 22:24

2

First note $3^{2n} = 9^n$

Then note $9^0 - 1$ is divisible by eight and $9^{n+1} - 9^n = 8*9^n$

edited Oct 16 '14 at 22:24

egreg

238,574

answered Oct 16 '14 at 21:52

Pieter21

3,475

I took the liberty of fixing the base step of the induction. – egreg Oct 16 '14 at 22:24

score 1 · Answer 3 · answered Oct 16 '14 at 21:54

Assume $3^{2n}-1$ is divisible by $8$. $$3^{2(n+1)}-1=3^{2n}3^{2}-1=9*3^{2n}-1=9*3^{2n}-9+8=9\big(3^{2n}-1\big)+8$$ $3^{2n}-1$ and $8$ are both divisible by $8$, therefore the sum is also divisible by $8$. This along with the proof that the statement holds true for $n=1$ proves this statement by induction.

Proof formula with induction

3 Answers3