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 am having a hard time trying to solve the following problem. I am very novice to the topic of growth functions at the moment. I could use a little help with this problem.

Let $\preceq$ be the relation on growth functions defined by $f \preceq g$ if there is a constant $\lambda \ge 1$ such that $f(x) \le \lambda g(\lambda x + \lambda) + \lambda$ for all $x \in [0, \infty)$. Show that $\preceq$ is symmetric and transitive and that the relation $f \sim g$ - is defined to mean both $f \preceq g$ and $g \preceq f$.

share|improve this question
    
What have you tried? –  user5137 May 28 '12 at 4:53
    
I tried starting with the elementary concept of showing that something was symmetric, but it came out strange, and the last part of the question is confusing me. –  Rhonda May 28 '12 at 5:12
    
What is your definition of growth function? –  Brian M. Scott May 28 '12 at 5:19
    
Any non- decreasing function $f : [o, \infty) \rightarrow [o, \infty)$ is a growth function. –  Rhonda May 28 '12 at 5:22
    
Then $\preceq$ isn’t symmetric; I’ll post an answer in a minute. –  Brian M. Scott May 28 '12 at 5:23

1 Answer 1

The relation $\preceq$ isn’t symmetric.

Let $f(x)=1$ and $g(x)=x$ for all $x\in[0,\to)$. Then with $\lambda=1$ we have

$$1=f(x)\le x+2=g(x+1)+1$$ for all $x\in[0,\to)$, so $f\preceq g$. Now suppose that $g\preceq f$; then there is some $\lambda\ge 1$ be such that $$x+1=g(x)\le\lambda f(\lambda x+\lambda)+\lambda=2\lambda$$ for all $x\in[0,\to)$, which is clearly impossible. Thus, $f\preceq g\not\preceq f$, and $\preceq$ is not symmetric.

To show that $\preceq$ is transitive, you must show that if $f,g$, and $h$ are functions such that $f\preceq g$ and $g\preceq h$, then $f\preceq h$. Your hypothesis gives you constants $\lambda,\mu\ge 1$ such that $$f(x)\le\lambda g\big(\lambda x+\lambda\big)+\lambda\tag{1}$$ and $$g(x)\le\mu h\big(\mu x+\mu\big)+\mu\tag{2}$$ for all $x\in[0,\to)$, and you want to show that there is a constant $\nu\ge 1$ such that $$f(x)\le\nu h\big(\nu x+\nu\big)+\nu$$ for all $x\in[0,\to)$. If you combine $(1)$ and $(2)$ in the most obvious way, you get

$$\begin{align*} f(x)&\le\lambda\Big(\mu h\big(\mu(\lambda x+\lambda)+\mu\big)+\mu\Big)+\lambda\\ &=\lambda\mu h\big(\lambda\mu x+\lambda\mu+\mu\big)+\lambda\mu+\lambda\;. \end{align*}$$

What happens now if you take $\nu=\lambda\mu+\lambda+\mu\,$?

share|improve this answer

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.