I'm reading through a proof for $4^n-1 $ is divisible by $3$ and it has a step which I'm not understanding.
The induction step:
$4^{n+1}-1=4 \cdot 4^{n}-1 = 3\cdot4^n+(4^n-1)$
Can anyone explain this transition:
$4 \cdot 4^{n}-1 = 3\cdot 4^n+(4^n-1)$
You want to show that $4^n-1$ is divisible by $3$ for all $n\geq 1$. Clearly it holds for $n=1$. Now suppose it holds for $n\geq 1$. Then $$4^{n+1}-1=4 \cdot 4^n-1=(3+1)\cdot 4^n-1=3\cdot 4^n+(4^n-1).$$
Clearly $3\cdot 4^n$ is divisible by $3$. By assumption $4^n-1$ is divisible by $3$ as well. Hence the sum is divisble by $3$ and thus $4^{n+1}-1$ is divisible by $3$. By induction we're done.