# Explain this transition: $4 \cdot 4^{n}-1 = 3\cdot 4^{n}+(4^n-1)$

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)$

• $4\cdot 4^n=\underbrace{4^n+4^n+4^n}_3+4^n=3\cdot 4^n+4^n$ Sep 1, 2017 at 15:29

## 1 Answer

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.

• I understand these parts. The part I don't understand is the transition. So it doesn't answer the question// Sep 1, 2017 at 15:31
• Ahh I see you clarified that 4=(3+1). Thanks Sep 1, 2017 at 15:32
• Yes, that's all there is to it. Sep 1, 2017 at 15:32