Via inductive proof show that $3^{2n}-1$ is divisible by 8 for all natural numbers n
The reason why that I was confused in this problem was because my steps has gotten me nowhere useful as shown below:
(I've omitted the words for the inductive proof for the sake of simplicity)
=$3^{2(k+1)}-1$
$=9-3^{2k}-1$
$=8-9*3^k$
But this has gotten me nowhere and I was wondering if there was any other way to prove this with inductive proof
$\endgroup$ 42 Answers
$\begingroup$Since the title asks for a proof by induction I will provide one. For a non-inductive proof see user8012403's answer.
For base case, $n = 0$, we simply note $3^{2\cdot0}-1 = 0$ which is a multiple of 8.
For the inductive step, suppose that $8|3^{2n}-1$. Then note that $$3^{2n+2}-1 = 9\cdot3^{2n}-1=(3^{2n}-1)+(8\cdot3^{2n}).$$
Both terms on the right are multiples of 8 and thus their sum is too; hence we're done.
$\endgroup$ $\begingroup$Let $P(n)$ be the proposition.
When $n=1$, we have $3^2 -1=8$, thus $P(1)$ is true. Assume that $P(k)$ is true for some $k\in \mathbb{Z}^{+}$, i.e. $\exists k\in \mathbb{Z}^{+}, 3^{2k}-1\equiv 0 \mod 8\iff 3^{2k}\equiv 1 \mod 8$
now, when $n=k+1$,
$3^{2k+2}-1=9*3^{2k}-1$
$\equiv 9*1-1 \mod 8$
$\equiv 0 \mod 8$
By the principle of mathematical induction, $P(n)$ is true for $\forall n\in \mathbb{Z}^{+}$
Thanks Steven.
$\endgroup$ 6
