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 with it a bit 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?
For the upper bound, consider $a=1, x_0=1$:
$$\forall x\in \Bbb N, x\ge x_0\\ 1\cdot 2^x\ge 2^x-x^2\\ 0\ge -x^2$$
For the lower bound, consider $a=\frac 12, x_0=8$:
$$\begin{align}x\in \Bbb N&, y=x+x_0-1\\ \text{to show: }\;a\cdot 2^y&\le 2^y-y^2\\ \frac 12 2^{x+x_0-1}&\le 2^{x+x_0-1}-(x+x_0-1)^2\\ 2^{x+6}&\le 2^{x+7}-(x+7)^2\\ 2^{x+6}&\ge (x+7)^2\end{align}$$
It should be a simple matter to continue from here, whether directly or with induction.