Use induction to prove that $3|(4^n − 1) $ for any integer $n \geq 0$ Use induction to prove that :

$ 3 |(4^n − 1)$ for any integer $n ≥ 0$

Hint: If $k \geq 0$ is an integer then
$4^{(k+1)} = 4\cdot4^k = 3 \cdot4^k + 4^k$.
Honestly have no idea how to even start this one
 A: Using Induction


*

*For $k = 0$, we have $3|0$, which is true.

*Assume $3|(4^{k}-1)$. So we can say $4^k -1 = 3q$

*Now multiply both sides by $4$ :
$$\begin{align}4^{k+1}-4 &= 12q \\
\implies4^{k+1} -1 &= 3(4q+1)\end{align}$$
Thus $P(k) \implies P(k+1)$ so that $P(k)$ is true for all naturals.

Using Binomial Theorem
I think you seek to prove  $3 | (4^k - 1)$. Consider the binomial expansion of $(4-1)^{k}$
$$(4-1)^k = \binom{k}{0}4^k  - \binom{k}{1} 4^{k-1} \dots (-1)^k\binom{k}{k}$$
Now take case for odd and even $k$.


*

*For odd $k$, $3^k = 4q-1$. Hence we get our result.

*For even $k$, $3^k = 4q+1 =4(q-1)+6-1$. Then again our result follows
A: Base Case : $n=0$,$~3 \vert 0$ is true.
Now suppose $3 \vert 4^n -1$ for some $n \ge 0$.
We've to prove $3 \vert 4^{n+1}-1$ is also true. 
$3 \vert 4^{n}-1 \implies 3 \vert4(4^n-1) \implies 3 \vert4(4^n-1)-3 \implies 3 \vert4^{n+1}-1$
Hence proved :)
A: if $n=1$ it is true because $4^1-1=3$
Now suppose that $4^n -1$ is a multiple of $3$ and let's prove that
$4^{n+1}-1$ is a multiple of $3$, too $\quad(*)$
The inductive hypothesis is that $4^n -1$ is a multiple of $3$ that is $4^n-1=3k$ for some $k$ we can write as $4^n=3k+1$
back to $(*)$
$4^{n+1}-1=4\cdot 4^n -1=4(3k+1)-1=12k+4-1=12k+3=3(4k+1)$
which proves that $4^{n+1}-1$ is a multiple of $3$
Hope this is useful
A: Another way of doing it using modular arithmetics


*

*$k=0$, $4^0-1=0$ and $3 \mid 0$

*$k=1$, i.e. $4 \equiv 1 \pmod{3}$ (which is the same as $3 \mid 4 -1$)

*we assume it is true for $4^k \equiv 1 \pmod{3}$ (which is the same as $3 \mid 4^k -1$)

*from $(2)$ and $(3)$ and the fact that $\color{red}{a \equiv b \pmod{n} \text{ and } c \equiv d \pmod{n} \Rightarrow ac \equiv bd \pmod{n}}$ we have
$$4^k \cdot 4 \equiv 1\cdot 1 \pmod{3}$$ or $$4^{k+1} \equiv 1 \pmod{3} \Leftrightarrow 3 \mid 4^{k+1}-1$$

A: The hint says it all.
Let $ k = 0 $, then $4^k \equiv 1 \mod 3$.
Suppose, for $k=n$ you have $4^k \equiv 1 \mod 3$, now
for $k = n+1$, per hint $$4^{n+1} = 3 \cdot 4^n + 4^n \equiv 4^n \equiv 1 \mod 3$$
What that mean is $$4^n - 1 = 3 \cdot m$$ for some natural $m$.
A: The case $k = 0$ is self-evident: $3 \mid 0$.
Consider that
$3 \mid 4 - 1, \tag 1$
which is the case $k = 1$;. then since we have
$4(4^k - 1) + 3 = 4^{k + 1} - 4 + 3 = 4^{k + 1} - 1, \tag 2$
if we assume
$3 \mid 4^k - 1, \tag 3$
and recall as in (1) that  
$3 \mid 3, \tag 4$
we see that
$3 \mid 4(4^k - 1) + 3 \tag 5$
directly follows.  Thus, via (2), we obtain
$3 \mid 4^{k + 1} - 1; \tag 6$
So much for an inductive proof of (6).  As simple as this is, an even simpler (non-inductive) proof may be had by observing that
$4^{k + 1} - 1 = (2^2)^{k + 1} - 1 = (2^{k + 1})^2 - 1 = (2^{k + 1} - 1)(2^{k + 1} + 1), \tag 7$
and that $3$ must divide at least one of the three consecutive integers
$2^{k + 1} - 1, 2^{k + 1}, 2^{k + 1} + 1; \tag 8$
since $3 \not \mid 2^{k + 1}, \tag 9$ 
we must have
$3 \mid 2^{k + 1} - 1 \vee 3 \mid 2^{k + 1} + 1, \tag{10}$
and in either case we see that
$3 \mid (2^{k + 1} - 1)(2^{k + 1} + 1), \tag{11}$
from which, by (7), (6) becomes evident as well.
