This question is motivated by teaching : I would like to see a completely elementary proof showing for example that for all natural integers $k$ we have eventually $2^n>n^k$.

All proofs I know rely somehow on properties of the logarithm. (I have nothing against logarithms but some students loathe them.)

Is there a brilliant "proof from the book" for this inequality (for example given by an explicit easy injection of a set containing $n^k$ elements into, say, the set of subsets of $\lbrace 1,\ldots,n\rbrace$ for $n$ sufficiently large)?

A fairly easy but somewhat computational proof (which leaves me therefore unhappy):

Given $k$ choose $n_0>2^{k+1}$. For $n>n_0$ we have \begin{align*} &\frac{(n+1)^k}{2^{n+1}}\\ &=\frac{1}{2}\left(\frac{n^k}{2^n}+\frac{\sum_{j=0}^{k-1}{k\choose j}n^j}{2^n}\right)\\ &\leq \frac{n^k}{2^n}\left(\frac{1}{2}+\frac{2^k}{2n_0}\right)\\ \leq \frac{3}{4}\frac{n^k}{2^n} \end{align*} showing that the ratio $\frac{n^k}{2^n}$ decays exponentially fast for $n>n_0$.

A perhaps more elementary but slightly sloppy proof is the observation that digits of $n\longmapsto 2^{2^n}$ (roughly) double when increasing $n$ by $1$ whilst digits of $n\longmapsto (2^n)^k$ form (roughly) an arithmetic progression. (And this "proof" uses therefore properties of the logarithm in disguise.)