2
$\begingroup$

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 Answers 1

5

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

  • 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.2011-11-29