divisibility - Prove by induction that $forall n inmathbb N$, $3mid4^{n}-1$.

Prove by induction that $\forall n \in\mathbb N$, $3\mid4^{n}-1$.

1) For $n = 1$ the statement is obviously true.

2) Now what about $n+1$? I was thinking of writing $4^{n}-1$ as $2^{2n}-1$ and then $4^{n+1}-1 = 2^{2n+2}-1$ but that got me nowhere.

Answer

Hint: $\;4^{n+1}-1=4 \cdot 4^n-1=(3+1)\cdot 4^n-1=3\cdot 4^n + 4^n-1\,$.

The non-induction proofs are more direct, though:

• $\;4^n-1 =(4-1)(4^{n-1}+4^{n-2}+\ldots+1)$





• $\;4^n-1=(3+1)^n - 1 = \ldots$