Prove that $4^n+ 1$ is not divisible by $3$ For all integers $n \ge 0$, prove that the value $4^n + 1$ is not divisible by 3.
I need to use Proof by Induction to solve this problem. The base case is obviously 0, so I solved $4^0 + 1 = 2$. 2 is not divisible by 3.
I just need help proving the inductive step. I was trying to use proof by contradiction by saying that $4^n + 1 = 4m - 1$ for some integer $m$ and then disproving it. But I'd rather use proof by induction to solve this question. Thanks so much.
 A: Induction step:
$$4^{n+1}+1=3\cdot 4^n+4^n+1\equiv4^n+1\mod 3$$

By the way, by recurrence,
$$4^n\equiv1\mod3,$$
$$4^n+1\equiv2\mod3,$$
$$4^n+2\equiv0\mod3.$$
A: I think that if you need to use induction, instead of proving "$4^n+1$ is not divisible by $3$", you should prove the more specific "$4^n+1$ has remainder $2$ when divide by $3$".
$$4^n+1=3k+2\implies4^n=3k+1\implies4^{n+1}=12k+4$$
$$\implies4^{n+1}+1=12k+5\implies4^{n+1}+1=3(4k+1)+2$$
A: The statement is true for $n=0$. Now, let it be true for $n=k$. Also, if possible, let it be false for $n=k+1$. Then, $4^{k+1} \equiv -1 \pmod{3} \implies 4 \cdot 4^k \equiv -1 \pmod{3} \implies 4^k \equiv -4 \pmod{3} \equiv -1 \pmod{3}$ (since $4^{-1} \equiv 4 \pmod{3}$). So, $3 \mid 4^k+1$, a contradiction. Hence, it's true for $n=k+1$. Hence the proof. 
A: Hint: Suppose $3$ does not divide $4^{n}+1$ for some $n\in\{0,1,\ldots\}$.
If $3$ divides $4^{n+1}+1$,
$$
0\equiv4^{n+1}+1\equiv4^{n}4+1\equiv \text{ } ?\text{ (mod }3\text{)}.
$$
(I have left out a step which you should fill in to arrive at a contradiction)
A: Your induction step could look like this: 
Suppose $4^n + 1 \equiv 1\pmod{3}$, then $4^n \equiv 0\pmod{3}$, so
$$
4^{n+1} + 1 \equiv 4(4^n) + 1 \equiv 1\pmod{3}
$$
and if $4^n+1 \equiv 2\pmod{3}$, then $4^n \equiv 1\pmod{3}$, so
$$
4^{n+1} +1 \equiv 4+1\pmod{3} = 2\pmod{3}
$$
A: Hint: $4^n-1=4^n-1^n$ is divisible by $3$ (why?).
A: Hint $\ \ f_n =\, 4^n\!+1\ \Rightarrow\,\ f_{n+1}\!-f_n =\! \overbrace{\color{#c00}3\cdot 4^n}^{\large 4^{\Large n+1}-4^{\Large n} }\! $ so $\,\ \color{#c00}3\mid f_{n+1}\!\iff \color{#c00}3\mid f_n$
Remark $ $ Said  $\,{\rm mod}\ 3\!:\  f_{n+1}\equiv f_n\ $ so by induction $\,f_n\equiv f_0 \equiv 2,\ $ so $\ f_n\not\equiv 0$ 
But using congruences it is clearer to prove by induction  $\,4\equiv 1\,\Rightarrow\, 4^n\equiv 1^n\equiv 1\,$ (special case of Congruence Power Rule). $ $ Then $\,f_n = 4^n+1\equiv 1+1\equiv 2\,$ by the Congruence Sum Rule.
A: I can see a superset proof:  If you transform it into  $2^{2n} + 1$, it's a well known proof that shows it's not divisible by 3.  (maybe the original answer gave it away too much...)
A: $$4\equiv1\pmod3$$
$$\implies4^n\equiv1^n\pmod3$$
Also,$1\equiv1\pmod3$
Adding,$$4^n+1\equiv2\pmod3$$
