# Is $n=\mathcal{O}(n+1)$?

With $c=1$ and $n_0=0$ the statement

$$(\forall \mathbb{N}_0\ni n>n_0)[n\leq c\cdot (n+1)]$$

is obviously true. Does this suffice for the proof of $n=\mathcal{O}(n+1)$?

Another idea was this one:

$$\limsup\limits_{n\to\infty}\left|\frac{n}{n+1}\right|=\limsup\limits_{n\to\infty}\left|\frac{\frac{\text{d}n}{\text{d}n}}{\frac{\text{d}(n+1)}{\text{d}n}}\right|=\limsup\limits_{n\to\infty}\left|\frac{1}{1}\right|=1,\;\text{with }0<\limsup\limits_{n\to\infty}\left|\frac{n}{n+1}\right|<\infty\Rightarrow n=\mathcal{O}(n+1)$$

Would this suffice?

-

## 1 Answer

Yes, the first obvious fact suffices as proof.

It shows directly that the definition of $O(n+1)$ is satisfied. Nothing more to wish for there.

However, the notation $\forall \mathbb{N}_0\ni n>n_0$ is somewhat nonstandard. People really like to have the bound variable immediately follow the quantifier sign, so you should write $\forall n\in\mathbb N_0.n>n_0\Rightarrow \cdots$ -- or just $\forall n>n_0$.

-
This notation is weird I know, so i will change this one. In a few minutes I will accept your answer, when the system allows me to do so. – Christian Ivicevic Nov 29 '11 at 20:58