How can we show that $\lim_{n \to +\infty} f(n)=+\infty$?

We suppose that $\lim_{n \to +\infty} f(n)=+\infty$.

I want to prove that if $f(n)=O(g(n)), c \in \mathbb{R}$, then $f(n)+c=O(g(n))$ .

$f(n)=O(g(n))$

That means that $\exists c_1>0, n_2 \in \mathbb{N}$, such that $\forall n \geq n_2$:

$$f(n) \leq c_1 g(n)$$

$\lim_{n \to +\infty} f(n)=+\infty$

This means that $\forall \epsilon>0 \ \exists n_0$, such that $\forall n \geq n_0$, $$f(n)> M$$

How can we use this, in order to show that $f(n)+c=O(g(n))$ ?

• This is false, $c = O(1)$ for any $c\in\mathbb R$, so you can set $f=0$. – user2345215 Nov 29 '14 at 14:30
• The assumption that $f(n)=O(g(n))$ and $f(n)+c=O(g(n))$ does not imply that $\lim\limits_{n \to +\infty} f(n)=+\infty$ (even assuming $c\ne0$). – Did Nov 29 '14 at 14:30
• I edited my post.. Does it make sense now? – evinda Nov 29 '14 at 14:38

Assume that $\liminf |f|\gt0$, then, for every finite $c$, $f+c\in O(f)$.
To apply this to your setting, note that the hypothesis that $\lim f=+\infty$ implies that $\liminf |f|\gt0$, and that if $f+c\in O(f)$ and $f\in O(g)$ then $f+c\in O(g)$.
Now can you prove the result above? One should start with the hypothesis that $\liminf |f|\gt0$, hence $|f(n)|\geqslant a$ for some $a\gt0$, for every $n$ large enough, say, for every $n\geqslant N$, hence $|f(n)+c|\leqslant$ $____$ for every $n\geqslant N$, hence...