How can I prove that $3| (4^n - 1)$ or 3 divides $4^n - 1$?
I have started it by induction, so the basis works and I assumed the induction hypothesis $3| (4^n - 1)$ but do not know how to use it to simplify $3| (4^{(n + 1)} - 1)$. could anyone help me to show this?
To prove by that the next term in the sequence $4^{n+1}-1$ is also divisible by $3$, it makes sense to prove that the difference is divisible by $3$. The difference between two consecutive terms is $$(4^{n+1}-1)-(4^n-1)=4^{n+1}-4^n=4^n(4-1).$$
Use the identity $q^{n+1}-1 = (1+q+\ldots+q^n)(q-1)$.
For $q=4$, we get $4^{n+1}-1 = a\cdot (4-1)=3a$ for some number $a$.
To prove by induction you can do this: $$ 4^{n+1}-1=4^{n+1}-4+4-1=4(4^n-1)+3.$$ Hence, $3\lvert 4^{n+1}-1$.
$n=0$√, let $n \ge 1$.
$(3+1)^n -1= $
$\sum_{k=0}^{n}\binom{n}{k}3^{n-k}1^k-1=$
$\sum_{k=0}^{n-1}\binom{n}{k}3^{n-k} +1-1$;
The binomial expression is divisible by $3$.
$$4=3+1$$ So: $$4^n-1=(3+1)^n-1$$ Which by FOIL, has all but one term of the power expansion divisible by 3, leaving $$1^n=1$$ and $$1-1=0$$ This shows regardless of natural number n, $$3\mid 4^n-1$$