Proof by induction: $2^{2n}-1$ is a multiple of $3$

Question

I'm learning proofs by induction and I'm a little confused on how they work exactly. This is what I have.

Theorem: $\forall n\in\mathbb N_0$, $2^{2n}-1$ is a multiple of 3.

old proof with mistakes:

Base: $n=1$

$2^{2(1)}-1 = 4-1 = 3$

$3 = 3m, m\in\mathbb N$

$3$ is a multiple of $3$, so the theorem holds for the base case.

Step: $n\ge 2$

Induction hypothesis: $2^{2n}-1:=3m, m\in\mathbb N$

Induction conclusion: $2^{2(n+1)}-1=3m, m\in\mathbb N$

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

= $4*2^{2n}-1$

= $4*3m$ by the induction hypothesis

= $12m$

= $3(4m)$

$2^{2(n+1)} = 3m, m\in\mathbb N$

So $2^{2n}-1$ is a multiple of 3 $\forall\in\mathbb N$

Is the logic behind this correct?

Edit: corrections:

Step: n ≥ 2

Induction hypothesis: $2^{2n}-1=3m, m ∈ Z$

Induction conclusion: $2^{2(n+1)}-1=3m, m ∈ Z$

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

= $4*2^{2n}-1$

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

= $4*3m+3$ by the induction hypothesis

=$12m+3$

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

$4m+1\in\mathbb N$, so $2^{2n}-1$ is a multiple of 3 $\forall n\in\mathbb N_0$.

Answer 1

You have applied the induction hypothesis wrongly. We have $4 (2^{2n}) -1=4 (2^{2n}-1)+3=4(3m)+3=3(4m+1)$

Answer 2

Long comment (due to the limited № of words in the comment section).

I don't know what your initial task was, but the statement holds for all the natural numbers and 0, i.e., $\forall n\in\mathbb N_0$. One might argue wether $0\in\mathbb N$ or $0\notin\mathbb N$, depending on the convention in your country, but for $n=0$: $$\left(2^{2n}-1\right)\in\mathbb N_0.$$

You don't need to use $m$ in the base case because obviously $3\mid 3$ so it's redundant. In the induction step I would say: Let $3\mid 2^{2n}-1$ for some $n\in\mathbb N$. If you use strong induction that I believe is unnecessary here, you would assume the statement: $$P(n)\equiv 3\mid 2^{2n}-1$$ holds for all numbers in the set :$\{0,1,\ldots,n\}$. Surely, $$n\in\mathbb N_0\implies n\in\mathbb Z, \forall n\in\mathbb N_0$$ because $\mathbb N\subset\mathbb Z$, but I wouldn't say $m\in\mathbb Z$ in this case so as to accent $m\in\mathbb N_0$ because $2^{2n}-1\ge 0\;\forall n\in\mathbb N$ so $m\ge 0$. Once again, ' for some $m\in\mathbb Z$' is correct, but weaker, while: $$\text{for some}\; m\in\mathbb N_0\:\text{is s stronger statement}$$

---

P.S. You could've also written: $$2^{2n}=3m+1, m\in\mathbb N$$ in the assumption and substitute $2^{2n}$ by $3m+1$ in the step.