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.

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

I wanted some help with a bounding question. The question asks that if $f$ is not an upper bound on $g$, is it a lower bound? $f,g: \mathbb{N} \to \mathbb{N} \cup \{\infty\}$.

By definition for an upper bound, there exists a constant $c$, there exists a constant $n_0$ such that $f(n) \le c \cdot g(n)$ for all $n > n_0$.

Negating that suggests for all $c$, for all $n_0$, $f(n) > c\cdot g(n)$.

So it would seem like the statement is true, but is it?


share|cite|improve this question
Try $g(n) = n$ and $f(n) = 0$ for even $n$ and $f(n) = n!$ for odd $n$. – Louis Jan 30 '13 at 16:14
Your don't negate the statement correct. It would be: $\exists n>n_0$ such that $f(n)>c\cdot g(n)$. – k1next Jan 30 '13 at 16:16
up vote 1 down vote accepted

Let $$f(n)=\begin{cases}1&n\text{ odd}\\n&n\text{ even}\end{cases}$$ $$g(n)=\begin{cases}1&n\text{ even}\\n&n\text{ odd}\end{cases}$$ Then $f$ is neither an upper nor a lower bound for $g$ in the sense of your question. Whatever positive real $c$ (and natural $n_0$ ) you choose, $f(n)\le cg(n)$ becomes false as soon as $n>c$ (and $n_0$) is even and $f(n)\ge cg(n)$ becomes false as soon as $n>\frac1c$ (and $n_0$) is odd.

Note that the negation of $$ \exists c\exists n_0\forall n>n_0\colon f(n)\le cg(n)$$ is rather $$ \forall c\forall n_0\exists n>n_0\colon f(n)> cg(n)$$ and that is not the definition of lower bound.

share|cite|improve this answer

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.