Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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|improve this answer
1  
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

 
discard

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.