Use the PMI to prove the following $4^{k}-1$ is divisible by 3.

Question

$4^{n}-1$ is divisible by $3.$

(i) Basis Step: $P(1)$is true because $4^1 -1=3 $ and $3\mid3$.

(ii) Suppose $P(k)$ is true for induction hypothesis $3\mid4^{k}-1$.

Show $(k+1)$ is true $3\mid4^{k+1}$

Now here is where things gets tricky.

$\Rightarrow 4^{k+1} -1 = \left(4^{k}*4 \right)-1 =$

I cannot seem to figure out how one factors this any further. I just cannot seem to make it divisible by 3. Could someone show me how to do this?

Answer 1

For $n\geq1$, let $S(n)$ denote the statement $$ S(n) : 3\mid(4^n-1)\Longleftrightarrow4^n-1=3m, m\in\mathbb{Z}. $$ Base case ($n=1$): $S(1)$ says that $3\mid(4^1-1)$, and this is true.

Inductive step: Fix some $k\geq1$, and assume that $S(k)$ is true where $$ S(k) : 3\mid(4^k-1)\Longleftrightarrow4^k-1=3\ell, \ell\in\mathbb{Z}. $$ To be proved is that $S(k+1)$ follows where $$ S(k+1) : 3\mid(4^{k+1}-1)\Longleftrightarrow4^{k+1}-1=3\eta, \eta\in\mathbb{Z}. $$ Beginning with the left-hand side of $S(k+1)$, \begin{align} 4^{k+1}-1&= 4(4^k-1)+3\tag{rearrange}\\[1em] &= 4\cdot3 \ell+3\tag{by $S(k)$}\\[1em] &= 3(4\ell+1)\tag{factor out 3}\\[1em] &= 3\eta,\tag{$\eta=4\ell+1, \eta\in\mathbb{Z}$} \end{align} we end up at the right-hand side of $S(k+1)$, completing the inductive step.

Thus, by mathematical induction, the statement $S(n)$ is true for all $n\geq1$. $\blacksquare$

Answer 2

Inductive assumption: $3 \mid (4^k-1)$, and therefore $(4^k-1) = 3m$ for some $m$.

$4(4^k-1) = 4^{k+1} -4 = 4^{k+1}-3-1$

so $4^{k+1}-1= 4(4^k-1)+3 = 12m+3$ which is divisible by $3$, completing the induction.

Answer 3

Rewrite statement (*) as $(3+1)^n =3k+1.$ When $n=1$ let $k=1.$

Assume $(3+1)^n =3k+1 $. $(3+1)(3k+1)=3(3k+1)+3k+1=3(3k+1+k)+1 .$

Answer 4

$$4^{k+1}-1=4\cdot 4^k-1=4\cdot (4^k-1+1)-1=4(4^k-1)+4(4)-1=4(4^k-1)+15.$$ So $3|(4^k-1)\implies 3|(4^{k+1}-1).$

Answer 5

Let $S(n)$ be the statement: $4^{n}-1$ is divisible by $3$

Basis step: $S(1)$: $\hspace{5 mm}4^{(1)}-1=3$, which is divisible by $3$

Inductive step:

Assume $S(k)$ is true, i.e. assume that $4^{k}-1$ is divisible by $3$

$\hspace{59 mm}\Rightarrow 4^{k}-1=3A$; $A\in\mathbb{N}$

$\hspace{59 mm}\Rightarrow 4^{k}=3A+1$

$S(k+1)$: $4^{k+1}-1$

$\hspace{12.5 mm}=4\bullet{4^{k}}-1$

$\hspace{12.5 mm}=4\hspace{1 mm}(3A+1)-1$

$\hspace{12.5 mm}=12A+4-1$

$\hspace{12.5 mm}=12A+3$

$\hspace{12.5 mm}=3\hspace{1 mm}(4A+1)$, which is divisible by $3$

So, $S(k+1)$ is true whenever $S(k)$ is true.

Therefore, $4^{n}-1$ is divisible by $3$.