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.

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?

Thanks.

share|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)$. –  sonystarmap Jan 30 '13 at 16:16
add comment

1 Answer

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|improve this answer
add comment

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.