Prove $4^{n} -1$ is divisible by $3$ for all $n\geq1$

Question

I'm doing some homework, and can't seem to get my head around this inductive proof.

So far I have got:

Atom case: $4^1 -1 = 3$, so proved for basic case.

Closure:

Assume $4^k - 1$ is divisible by $3$, Show that $4^{k+1} -1$ is divisible by $3$.

So: $4^k-1 = 4^k\cdot4 -1$ but this is where I get stuck, unsure where to go from here.

Any help much appreciated.

Answer 1

Hint $ $ To induct $\rm\color{#c00}{multiply}$ the first two congruences below (using the Congruence Product Rule)

$$\begin{align} \bmod 3\!:\quad\ \ 4&\equiv 1\\[.3em] 4^{\large n}&\equiv 1\ \ \ {\rm i.e.}\ \ P(n)\\ \overset{\color{#c00}{\rm multiply}}\Longrightarrow\ 4^{\large n+1} &\equiv 1\ \ \ {\rm i.e.}\ \ P(n\!+\!1) \end{align}$$

Remark $ $ The proof is a special case of an inductive proof of the Congruence Power Rule, which is the straightforward inductive extension of the Product Rule.

If congruences are unfamiliar then we can instead use the Product Rule in Divisibility form:

$$\begin{align} {\rm mod}\,\ m\!:\, A\equiv a,\, B\equiv b&\ \ \,\Longrightarrow\,\ \ AB\equiv ab\qquad\text{Congruence Product Rule}\\[3pt] m\mid \color{#c00}{A-a},\ B-b&\,\Rightarrow\, m\mid \color{#0a0}{AB-ab}\qquad\text{Divisibility Product Rule}\\[4pt] {\bf Proof}\quad (A-a)B+a(B&-b)\, = AB-ab\end{align}$$

This way it is: $\,\ 3\,\mid\, \underbrace{4-1}_{\large \color{#c00}{A\,-\,a}},\, \underbrace{4^n-1}_{\large B\,-\,b}\,\Rightarrow\, 3\,\mid\, \underbrace{4\cdot 4^{\large n}-1\cdot 1}_{\large \color{#0a0}{AB\,-\,ab}} = 4^{\large n+1}-1$.

Note $ $ If you examine the common inductive proofs of this and similar results you will see that the proofs are precisely special cases of the above proof of the Product Rule (in either f0rm), e.g. see here where I explain that at length. Thus these Product Rules can be seen as the inductive essence of the matter. Bringing this innate arithmetical structure to the fore enables us to greatly simplify the inductive structure - so much so that the induction becomes completely obvious - boiling down to the obvious inductive proof that $\,1^n\equiv 1$.

Answer 2

$$ 4^{k+1} - 1 = 4\cdot4^k-1 = 3\cdot4^k + 4^k-1. $$

Therefore via induction we know $4^k-1$ is divisible by three, and the $3\cdot 4^{k}$ is clearly divisible by $3$.

Answer 3

You could do it this way: You have $4^k - 1 = 3m$, so $4^k=3m+1$. Now multiply both sides by $4$:

$$4^{k+1}=4(3m+1) = 12m+4 = 12m+3+1=3(4m+1)+1=3n+1$$

Thus, $4^{k+1}-1 = 3n$, as desired.

Answer 4

You can use the method of induction to prove the exercise.

For $n=1$, $4^n-1=4^1-1=3$ is divisible by $3$.

For $n=k$, assume $4^k-1$ is divisible by $3$, so $4^k-1=3m$ for some integer $m$.

For $n=k+1$, $4^n-1=4^{k+1}-1=4^k.4-4+3=4.(4^k-1)+3=4.3m+3=3.(4m+1)$ which is definitely divisible by $3$.

Thus, by the method of induction, our problem is solved for all $n\ge 1$

Answer 5

For any $n\ge1$ it will be the case that exactly one of $2^n-1,2^n, 2^n+1$ will be divisible by $3$.

Since $2^n$ is not divisible by $3$ then the product $(2^n-1)(2^n+1)=4^n-1$ must be divisible by $3$.

Answer 6

even though you don't know modular arithmetic, I'd add it can be done with: $4^n-1 \equiv 0 \pmod 3\implies 1^n-1\equiv 0 \pmod 3\implies 0\equiv 0\pmod 3$.
Simply because the remainder of 4 on division by 3 is 1.