Prove that $n^2\in \mathcal O(n^2-1)$.

Prove that $$\smash { n^2\in\mathcal{O}(n^2 -1)}$$

I don't quite understand what strategy I should use when trying to prove the following big $$\mathcal{O}$$ notation that doesn't include the use of limits. Whenever I try to find a $$C$$ when $$n>=2$$, I can never get it to be a positive real. Any advice would be appreciated.

• What do you mean "that doesn't include the use of limits"? Big $O$ is defined via limits. – lulu Mar 2 at 20:47
• using the definition of a limit. I want to try to solve it just using inequalities. – neet Mar 2 at 21:08
• You can not avoid the notion of a limit here. Why would you want to? At some point, whatever constant you like will imply an inequality that will only hold above some constant. If you pick $2$, for instance, then you need $x>\sqrt 2$. – lulu Mar 2 at 21:09

For any $$n\ge 2$$, you want $$n^2\le C(n^2-1)$$ which rerarranges to $$C\ge \frac{n^2}{n^2-1}=1+\frac1{n^2-1}$$ Since $$n\ge 2$$, we have $$1+\frac1{n^2-1}\le \frac43.$$ Therefore, for any $$C\ge \frac43$$, you have $$n^2\le C(n^2-1)$$ for all $$n\ge 2$$. This proves $$n^2\in \mathcal O(n^2-1)$$.

$$g(x) \in \mathcal{O}(f(x))$$ means that there exists a constant $$C$$ so that $$|g(x)| \leq C |f(x)|$$

In our case, notice that if $$C=3$$ for example, the inequality will be true

$$n^2 < C |n^2-1|$$

for $$n > n_0$$ for instance $$n_0$$ can be $$2$$ or $$3$$,...

$$C$$ can be $$2$$ also, or $$1.5$$, but $$C=1$$ wont work.

There is an implied limit in the big-O notation; it only makes sense "as $$n\to$$ something". In this case? $$n$$ is traditionally a name for an integer variable, and that something would be $$\infty$$.

If we used a different limit, we might get a different result. As $$n\to 0$$, $$n^2$$ is a smaller order than $$n^2-1$$; $$\lim_{n\to 0}\frac{n^2}{n^2-1}=0$$ and we could upgrade the $$O$$ to a $$o$$. As $$n\to 1$$, $$n^2\to 1$$ is bigger than $$n^2-1\to 0$$, and in that case we have $$n^2\not\in O(n^2-1)$$.