Show that $9|2^{2n+1}+2^{4n+1}-4$ 
Show that $9|2^{2n+1}+2^{4n+1}-4$ ( n is a positive integer):
  1-Using induction
  2-Don't use induction  

I have noticed that $2^m \equiv 2^{m+6} \pmod 9 $ but couldn't use it to solve the problem!
 A: It's true for all non-negative integers $n$.
Without induction:
$9\mid 2^{2n+1}+2^{4n+1}-4$ is equivalent to $$9\mid 2\cdot 2^{2n+1}+\left(2^{2n+1}\right)^2-8$$
$$=\left(2^{2n+1}+1\right)^2-9$$
I.e. $9=3^2\mid \left(2^{2n+1}+1\right)^2$, i.e. $3\mid 2^{2n+1}+1$, which is true,
because $2^{2n+1}\equiv (-1)^{2n+1}\equiv -1\pmod{3}$, because $2n+1$ is odd for all $n\in\mathbb Z$, $n\ge 0$.

With induction:
Clearly $9\mid 2^{2\cdot 0+1}+2^{4\cdot 0+1}-4=0$.
If $9\mid 2^{2n+1}+2^{4n+1}-4$, then
$$9\mid 2^{2(n+1)+1}+2^{4(n+1)+1}-4$$
$$=\left(2^{2n+1}+2^{4n+1}-4\right)+3\left(2^{2n+1}+5\cdot 2^{4n+1}\right)$$
because $$2^{2n+1}+5\cdot 2^{4n+1}\pmod{3}$$
$$\equiv (-1)^{2n+1}-(-1)^{4n+1}\pmod{3}$$
$$\equiv -1-(-1)\equiv 0\pmod{3}$$
A: Hint: If $a_n = 2^{2n+1}+2^{4n+1}-4$, then $a_n=20a_{n-1}-64a_{n-2}-180$
A: $2^{2n+1}+2^{4n+1}-4 = f(2^{2n})$ for $f(x)=2x^2+2x-4=2(x-1)(x+2)$.
Now $2^{2n} \bmod 9$ is $1,4,7,1,4,7,\dots$ and
$f(1) \equiv 0 \bmod 9$
$f(4) = 36 \equiv 0 \bmod 9$
$f(7) \equiv 0 \bmod 9$
So $f(2^{2n}) \equiv 0 \bmod 9$ for all $n$.
A: $2(4^{\large 2n}+4^{\large n}-2) \,=\, 2\,(\overbrace{(\color{#c00}{4^{\large n}\!-1})^{\large 2}}^{\Large (\color{#c00}{3k})^{\Large 2}}\!+\overbrace{3(\color{#c00}{4^{\large n}\!-1}))}^{\Large 3\,(\color{#c00}{3k})\ \ \ }\,$ is divisible by $\,9\,$ since $\,\color{#c00}{3\mid 4^{\large n}-1}\,$ (easily provable either by congruence arithmetic, the factor theorem, the binomial theorem, or induction).
A: $2x^2+2x-4=2(x^2+x-2)=2(x+2)(x-1)=2(x-1+3)(x-1)$ so, for $x=2^{2n}=4^n$,
$$
2^{2n+1}+2^{4n+1}-4=2(4^n-1+3)(4^n-1)
$$
and you just need to show that $3\mid 4^n-1$. 
No induction
Since $4\equiv1\pmod{3}$, the statement is proved.
With induction
The base case is obvious. If $4^n-1=3k$ with $k$ integer,
$$
4^{n+1}-1=4\cdot 4^n-1=4(3k+1)=12k+4-1=3(4k+1)
$$
