Wednesday, October 24, 2012

prove that 2^n > n^3 for n > 10



Basic Step:
When n = 10, the inequality 2^n > n^3 is true as 2^10 = 1024 > 1000

Inductive Step:
Assume n = k is true, where k ≥ 10, then
2^k > k^3 ................ (1)

we have for k >= 10

k^3 > 10k^2 > 4k^2 or  3k^2 + k^2 > 3k^2 + 3k + 1


So, from (1)
2(2^k)> 2(k^3)
=>2(2^k) > k^3 + k^3
=>2^(k+1) > k^3 + 3k^2 + 3k + 1
=>2^(k+1) > (k + 1)^3

So n = k + 1 is also true

so induction step is proved and hence proved
 

No comments: