Mathematical Induction (power of four exceeds multiple of three by one)

Question

The Question:

Prove by mathematical induction that $4^k - 1$ is divisible by $3$.

$p = (4^k-1) \bmod 3 = 0$.

The Answer:

If $k = 1$, $(4^k - 1) \bmod 3 = 0$, which is true.

Assuming $4^k - 1$ is true, lets continue to the induction step:

$4^{k+1}-1$

$(4^k \cdot 4^1) - 1$

$3\cdot 4^k + (4^k - 1)$

$3 \cdot 4^k$ is a multiple of 3, and $4^k - 1$ is true. Which means that the statement $p$ is true.

I understand everything up to the 2nd step where they have $(4^k \cdot 4^1) -1$. My question is why add $4^k-1$ to $3 \cdot 4^k$ in the 3rd step? What is the reasoning behind this?

Answer 1

This just reflects the simple fact that $4\cdot x=3\cdot x+x$.

Answer 2

because $3\times 4^k$ a multiple of 3. so you are not changing anything when modding.

Answer 3

Hint:

$4^k-1$

$P(1)=4^1-1=3$

Let $P(m)$ be true $\implies 4^m-1=3p$. Now prove for $4^{m+1}-1$ using $4^m=3p-1$