Notice for $k = 0$, $4^1 + 2^1 + 1^1 = 7$ which is prime. Now, suppose $n$ is not a multiple of 3, then $4^{3p + 2} + 2^{3p + 2} + 1$ will be composite since $4^{3p + 2} + 2^{3p + 2} + 1 \equiv 2 + 4 + 1 \textrm{(mod 7)}$, and $4^{3p + 1} + 2^{3p + 1} + 1$ will be composite since $4^{3p + 1} + 2^{3p + 1} + 1 \equiv 4 + 2 + 1 \textrm{(mod 7)}$. Hence $n$ is a multiple of 3. Generally, we use the following trick: Lemma. If $3 \not \vert n$ then $a^2 + a + 1 \vert a^{2n} + a^n + 1$. Proof. We'll split into 2 cases, i.e. $n = 3q + 1$ and $n = 3q + 2$. Case 1. $n = 3q + 1$ then $a^2 + a + 1 \vert a^{2n} - a^2 + a^n - a$ by the Division Algorithm. Notice that: a) $a^{6q + 2} - a^2 = a^2(a^{6q} - 1) = a^2(a^{3q} - 1)(a^{3q + 1}) = a^2(a^3 - 1)(a^{3(q-1)} + a^{3(q - 2)} + \cdots + a^3 + 1)(a^{3q} + 1)$ which is obviously true since $a^2 + a + 1 \vert a^3 - 1$. b) $a^{3q + 1} - a = a(a^{3q} - 1) = a(a^3 - 1)(a^{3(q - 1)} + \cdots + a^3 + 1)$ which is again, true, by the same reason as above. Case 2. $n = 3q + 2$ then $a^2 + a + 1 \vert a^{2n} - a + a^n - a^2$ by the Division Algorithm. Notice that: a) $a^{6q + 4} - a = a(a^{6q+3} - 1) = a(a^{3(2q + 1)} - 1) = a(a^3 - 1)(a^{3(2q)} + a^{3(2q - 1)} + \cdots + a^3 + 1)$ b) $a^{3q + 2} - a^2 = a^2(a^{3q} - 1) = a^2(a^{3(q-1)} + a^{3(q-2)} + \cdots + a^3 + 1)$ which are obviously true for the same reason. Thus if $n$ is not a power of three, we can take $n = 3^t \cdot q$ where $q$ is relatively prime to 3, and then substitute $a = 3^t$ on our lemma to get that it can't be prime, as desired.