How do I show that $2^x - x^2 \in \Omega(2^x)$?

Basically, I know that this means that $\exists a, x_0 \in \mathbb{R^+}, \forall x \in \mathbb{N}, a.2^x \leq 2^x - x^2$.

I worked around a bit with this and I seemed to have gotten something that makes sense for the case of an upper bound; $$2^x -x^2 < 2^x + x^2 < 2^{x+1} = 2.2^n $$ Now, if I were trying to find an upper bound, I'd have chosen $a = 2$ and $x_0 = 1$. How do I work the other way around(basically less than or equal to $2^x - x^2$ and prove this lower bound?


Here is the hint or outline of a proof.

  • Show that by mathematical induction, that $2x^2< 2^x$ for $x>7$.
  • Show that $\dfrac12\cdot2^x< 2^x-x^2$ for $x>7$
| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.