0
$\begingroup$

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

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

1 Answer 1

Reset to default
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.