<s>[INST] Proving an expression is composite I am trying to prove that $ n^4 + 4^n $ is composite if $n$ is an integer greater than 1. This is trivial for even $n$ since the expression will be even if $n$ is even. 
This problem is given in a section where induction is introduced, but I am not quite sure how induction could be used to solve this problem. I have tried examining expansions of the expression at $n+2$ and $n$, but have found no success.
I would appreciate any hints on how to go about proving that the expression is not prime for odd integers greater than 1. 
 [/INST] Some interesting factorizations of a polynomial of type $x^4+\text{const}$:
$$ x^4+4=(x^2+2x+2)(x^2-2x-2) \tag{1}$$
$$ x^4+1=(x^2+\sqrt[]{2}x+1)(x^2-\sqrt[]{2}x+1) \tag{2}$$
So one can ask, how to select the coefficients $a,b,c,d$ in
$$(x^2+ax+b)(x^2+cx+d) \tag{3}$$
such that all coefficients of the resulting polynomial are zero except the constant term and the coefficient of the 4th power. The latter is $1$.
If we expand $(3)$  we get
$$x^4+(c+a)x^3+(d+a c+b)x^2+(a d+b c)x+b d$$
And the coefficients disappear, if
$$ 
\begin{eqnarray}
c+a &=& 0 \\
d+ ac +b &=& 0 \\
ad+bc &=& 0
\end{eqnarray}
$$
When solving for $b,c,d$ we get
$$
\begin{eqnarray}
c &=& -a \\
b &=& \frac{a^2}{2} \\
d &=& \frac{a^2}{2} 
\end{eqnarray}
$$
and therefore
$$x^4+\frac{a^4}{4} = (x^2+a x+\frac{a^2}{2})(x^2-ax+\frac{a^2}{2})$$
For $a=2$ this gives $(1)$, $a=\sqrt[]{2}$ this gives $82)$ .
Substituting $a=2^{t+1}$ we get
$$x^4+4^{2t+1} = (x^2+2\cdot 2^t x+2^{2t+1})(x^2-2\cdot 2^tx+2^{2t+1})$$
Substituting $x=n=2t+1$ gives the required result for odd $n$.
</s>