Big-Oh notation asymptotic proof with faulty logic, trying to find the fault

Question

What is wrong with this proof? According to the problem the claim of the proof is correct, but its not a sufficient proof. I'm a bit stumped on this one as to why it's not a valid proof, it seems so to me. I need to figure out where the issue is, I don't need to actually solve the proof itself but the fact that I can't find the issue worries me that maybe I don't even know its an issue and do it in my own proofs. Any help is appreciated. Thank you

Let $f(n) = n^3 +n$. We want to prove that $f(n) \in O(n^3)$. By the definition of Big-Oh, $f(n) \in O(n^3)$ iff $f(n) \leq c*n^3$ for some $c > 0$ and all $n\geq n_0$. Using the definition of $f(n)$, $n^3 + n \leq c*n^3$. Let $c=2$ and $n_0 = 1$. By substituting in, we have $n^3 + n \leq 2n^3$. So, subtracting an $n^3$ from both sides, we get $n\leq n^3$. Dividing by n for both sides, we get $1\leq n^2$ which is true for all $n\geq n_0$. So, $f(n) \in O(n^3)$

Answer 1

For one, you suppose your conclusion from the start, which is usually not kosher in proof-writing, and it's generally hard to follow. That said, your logic in what you're trying to get to is okay - it's moreso the structure of your proof that's off to me than anything. Here's how I would rewrite your proof:

Notice, for all $n \ge 1$, we have $n \le n^3$. Therefore, $f(n) = n^3 + n \le n^3 + n^3 = 2n^3$. In our definition for big-O, this means our constant is $c=2$ and $n_0 = 1$. Thus by the previous calculation, $f \in \mathcal O(n^3)$

Alternatively, using a different definition of big-O, my preference would be that $f \in \mathcal O(g)$ iff $\limsup_{x \to a} |f(x)/g(x)|=1$. Then an alternative proof is

$$\limsup_{n \to \infty} \left| \frac{n^3 + n}{n^3} \right| = \limsup_{n \to \infty} \frac{1 + n^{-2}}{1} = 1$$ giving $n^3 + n \in \mathcal O (n^3)$. The steps between the two limits is that $n,n^3 \ge 0$ for $n \ge 0$, allowing us to remove the absolute value, and then we just divide by $n^3$ on top and bottom and calculate the obvious limit.