Simple proof; Show that $(4^n - 1)$ is divisible by 3 (Guided proof task) 
*

*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. 
 A: 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$
A: $(4^n-1)=(4-1)(4^{n-1}+4^{n-2}+...+4^{0})$
A: 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.
A: 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.
A: 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.
A: 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.
