Use the PMI to prove the following $4^{k}-1$ is divisible by 3. 
$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?
 A: 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. 
A: 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$
A: $$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).$
A: 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$.
A: 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 .$ 
