- First part of the task is just to show that $(4^n-1)$ actually is divisible by 3 for n=1,2,3,4. No problem.
Second step: is to show that $(4^n -1) = (2^n-1)(2^n+1)$ No problem, just algebra.
Third step is to explain that $(2^n-1)$,$2^n$,$(2^n+1)$ is three consecutive numbers. And that only one is divisible by three.
$2^n$ has two as a factor and is not divisible by 3. It can't be even. That leaves $(2^n-1)$ and $(2^n+1)$. The one with 3 as a factor seems to be random dependent on n.Fourth step, tie it all together.
Now, I'm not sure if I'm suppose to dig deeper into which of them is actually divisible by 3. Or has 3 as a factor. But knowing that one of them at the time (dependent on n) has indeed 3 as a factor implies that, in respect to the second step, 3 is a factor of $(4^n -1)$.
Is this all there is to it? Keep in mind that this is a really beginners proof task, not very formal. It's slightly funny going back to high school math after being scared to death by logic and descrete math at university-level. I just expect everything thing to be super complex.
$\endgroup$ 46 Answers
$\begingroup$$(4^n-1)=(4-1)(4^{n-1}+4^{n-2}+...+4^{0})$
$\endgroup$ 6 $\begingroup$Once you have show that $4^n-1=(2^n+1)(2^n-1)$, and one of the two factors is divisible by three, you have got that $3$ divides $4^n-1$.
If $2^n-1$ is divisible by three, write it as $3k$ then $4^n-1=3k(2^n+1)$ and therefore it is divisible by three (you should figure out how to write the argument in full).
The other case, where $2^n+1$ is the one divisible by three is symmetric, but you should write the details for that case as well, to practice your writing.
$\endgroup$ 3 $\begingroup$If $n$ is a positive integer,
using congruence formula, $4\equiv 1\pmod 3\implies 4^n\equiv 1^n\pmod 3\implies 4^n-1\equiv1-1\pmod 3$
Alternatively using binomial expansion, $4^n- 1=(1+3)^n-1$ $=(1+\binom n13+\binom n23^2+\cdots+\binom n{n-1}3^{n-1}+3^n)-1$ $=\sum_{1\le r\le n}3^r$ is clearly divisible by $3$
$\endgroup$ $\begingroup$One of any three consecutive numbers is divisible by $3$. Now, $2^n-1$, $2^n$, and $2^n+1$ are consecutive, and $3$ can't divide $2^n$, so it must divide one of the others and hence their product.
$\endgroup$ 1 $\begingroup$we can prove that $$3|(4^n-1),n\geq 1$$ using mathematical induction, for $n=1$ $$3|(4^1-1)$$ the statement is true. Suppose that statement is true for $n=k$ i.e $$3|(4^k-1)$$ now we prove for $n=k+1$ $$4^{k+1}-1=4^k4-1=3\times 4^k+(4^k-1)=$$ obviousley $3\times 4^k$ can be divided by $3$ and $4^k-1$ is divisible by $3$ by assumption.
$\endgroup$ $\begingroup$You can prove it very quickly by induction
- the expression is true for $n=0$, $n=1$, $n=2$ (you can check by hand)
- if the expression is true for $n$, then the expression is true for $n+1$.
Proof : $4^{(n+1)}-1 = 4\cdot (4^n-1)+3$, the first term is divisble by $3$ (step 2) and the second ($3$) also.
$\endgroup$ 1
