Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 5 down vote accepted

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$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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