I'm pretty sure I should let $a=k^2+k$, but I can only prove that it works for $a$ if $k+1\ge5$:
If $k+1\ge5$ then we can apply the fact that $x\ge5\to2^x>x^2$ for $x=k+1$, and get $2^{k+1}>(k+1)^2>k(k+1)=a$, so now $2^{k+1}>a$, therefore $2^a=2^{k(k+1)}=(2^{k+1})^k>a^k$.
But that is only for $a$ and $k+1\ge5$ when I need to prove it for all $n>a$ and $k>0$
How should a problem like this be approached? I figured out $a=k^2+k$ after a lot of trial and error (python scripts and graphing), which is probably not the best and most efficient way to solve something like this. I feel like I don't know the technique that should be used for a problem like this.
EDIT: Is this a valid proof?
(1): $x\ge5\implies 2^x\ge x^2$
Let $a=k^2+k$.
$Case\;1$. $k=1$. The inequality becomes $2^n\ge n$, which is already known to be true.
$Case\;2$. $k=2$. Then for any $n>a=k^2+k=6$, we can apply (1) and get $2^n\ge n^2=n^k$.
$Case\;3$. $k=3$. Same as $Case\;2$.
$Case\;4$. $k\ge4$. Take any $n>a$. Then $n=qk+r$ for some integers $q$ and $r$. Now $n>a$ and $a=k(k+1)$, so $q>k+1$. Then since $q> 5$, by (1), $2^q\ge q^2>q(k+1)=qk+q>qk+r=n$, so $2^q>n$. Therefore $2^{qk}>n^k$, and since $n\ge qk$, we have $2^{n}>n^k$, as required.
$\frac{n}{\log n} \overset{n\to\infty}{\to} \infty.\ $ So, given $\ k\in\mathbb{Z}^+,\ \exists\ a\in\mathbb{Z}\ $ such that $\frac{n}{\log n} > \frac{k}{\log 2}\ \forall\ n\geq a,\ \implies n\log 2 > k\log n, \implies e^{n\log 2} > e^{k\log n} \implies 2^n > n^ k\ \forall\ n\geq a.$