Is there a simpler proof that $n^2 = O(2^n)$?

Question

I am wondering if there is a simpler proof that $n^2 = O(2^n)$ which doesn't involve several layers of induction. My proof is as follows (sorry for the bad formatting).

Proof: $n^2 = O(2^n)$

We will show that $\exists k,c \in \Bbb R_{>0} : \forall n>=k, f(n) <= c*g(n)$

Let $k=2$ and $c=1$.

Basis step: f(2) <= g(2). That is, 2^2 <= 2^2, or 4<=4. But 4 = 4, so f(2) <= g(2) is true. Inductive step: Assume f(p) <= g(p). That is, p^2 <= 2^p. Equivalently, we have 2*p^2 <= 2*(2^p).
Consider the statement "f(p+1) <= g(p+1)". That is, "(p+1)^2 <= 2^(p+1). Equivalently, this is "p^2 + 2p + 1 <= 2*(2^p)".
Since 2*p^2 <= 2*(2^p) is true, if we show that p^2 + 2p + 1 <= 2*p^2, we have "p^2 + 2p + 1 <= 2*(2^p)" by transitivity of the inequality relation.
    We will show that p^2 + 2p + 1 <= 2*p^2.
    Subtracting p^2 from both sides, we equivalently have 2p + 1 <= p^2.
        We will show that 2p + 1 <= p^2 for all p >= 3.
        Basis step: 2*3 + 1 <= 3*3, or 7 <= 9, which is true
        Inductive step: Assume 2p + 1 <= p^2
        Consider the statement "2(p + 1) + 1 <= (p+1)^2", or "2p + 3 <= p^2 + 2p + 1", or subtracting 2p + 1, "2 <= p^2".
        Since "2p + 1 <= p^2" is true, if we show that "2 <= 2p + 1" is true, we have "2 <= p^2".
            We will show that "2 <= 2p + 1" for all p>=4
            Basis step: 2 <= 2*4 + 1, or 2 <= 9, which is true
            Inductive step: Assume 2 <= 2p + 1.
            Consider the statement "2 <= 2(p + 1) + 1", or "2 <= 2p + 3", or "0 <= 2p + 1".
            Since "2 <= 2p + 1" is true, if we show that "0 <= 2" is true, we have "0 <= 2p + 1".
            But 0 < 2.
            Q.E.D.
        Q.E.D.
    Q.E.D
We have p^2 + 2p + 1 <= 2*(2^p). That is, "f(p+1) <= g(p+1)".
Thus, if f(p) <= g(p), then f(p+1) <= g(p+1).
We have completed the inductive step, so for all n >= 2, n^2 <= 1*2^n. Q.E.D.

Answer 1

Inductive step:

$n^2 + 2n + 1 \le 2\cdot 2^n = 2^n + 2^n$

By the inductive hypothesis, the first $2^n > n^2$ and the other $2^n > n^2 > 2n + 1$ so sum both to get $2^{n+1} = 2^n + 2^n > n^2 + 2n + 1 = (n+1)^2 $ QED

Answer 2

$$4\le\sqrt2^4.$$

For $n\ge4$, $n+1<\sqrt2n$, so that $$n\le\sqrt2^n\implies n+1<\sqrt2n\le\sqrt2\sqrt2^n.$$

Squaring,

$$n^2\le2^n\implies(n+1)^2\le2^{n+1}.$$

Answer 3

It is a fundamental principle of set theory that $|S|<\bigl|{\cal P}(S)\bigr|$ for any set $S$. This implies $m<2^m$ for all $m\geq0$. For given $n\geq0$ we therefore have $${n\over2}\leq\left\lceil{n\over2}\right\rceil<2^{\lceil n/2\rceil}<2^{{n\over2}+1}\ .$$ From this we immediately obtain $$n^2\leq 16\cdot 2^n\qquad(n\geq0)\ .$$