Question

Use the Generalized PMI to prove:
2^n > n^2, for all n > 4

First of all, it's true for n=5.
Then to prove it for n+1...
Assume 2^n > n^2.
Then 2^(n+1) = 2*2^n
> 2*n^2
> 2*(4n) since n>4 => n^2>4n

I'm stuck there.

Answer 1

First of all, for n=5,
32=2^532>5^2=25
therefore, it's true for n=5.

Then to prove it for n+1...
Assume 2^n > n^2
(n+1)^2
=(n+1)^2/n^2 * n^2
=(1 + 2n/n^2 + 1/n^2) * n^2
=(1 + 2/n + 1/n^2) * n^2
≤(1 + 2/5 + 1/5²) * n^2 for n>4
=1.44n^2
<2*2^n
=2^(n+1) .....QED