Question

Prove for each n ∈ ℤ+, n > 3, 2^n >= n^2

Answer 1

\[2^n \ge n^2\]
then:
\[n \ge 2\log_2n\]
then:
\[\frac{n}{2} \ge \log_2n\]

Answer 2

this is true for 4

Answer 3

\[\frac{d(n/2)}{dn}=(1/2)\]

Answer 4

\[\frac{d(\log_2n)}{dn}=\frac{1}{n*\ln2}\]

Answer 5

therefore, for n > 2/ln(2) (2.88) n/2 grows faster than log_2n

Answer 6

So basically, it satisfies this relationship for 4, and then the LHS grows faster than the RHS

Answer 7

Now, first lets Prove n^2>2n+1 for n>3
WHEN n=4,
n^2>2n+1 ( TRUE)
Now, when n=n+1
(n+1)^2>2(n+1)+1
n^2+2n+1>2n+2+1
n^2>2 (WHICH IS ALWAYS TRUE when n>3)
Thus, n^2>2n+1 for n>3

NOW,
WHEN n=4 then 2^n>=n^2 (TRUE)
WHEN n=5 then 2^n>n^2 (TRUE)
WHEN n=n+1 then 2^(n+1)>(n+1)^2
2*2^n>n^2 + (2n+1)
This is true because when n=5, 2^n>n^2 AND 2^n>n^2>2n+1
Thus 2*2^(n+1)>(n+1)^2 is true for all n>4
SO,
2^n>=n^2 for n>3