0
$\begingroup$

At the moment I am hearing the lecture named geometric group theory. In the last exercise we got the following exercise: Let $f,g:\mathbb{N}\mapsto \mathbb{R}_{\geq 0}$. We say that $f\leq g$ if there exists a constant $C$, such that

$f(n)\leq C*g(C*n+C)+C*n+C$

We say that $f\sim g$ if $f\leq g$ and $g\leq f$. The exercise is to show that this defines an equivalence realtion on these functions. My problem is to show the reflexivity, because I have no idea how I can choose the C such that I can easy see that $f\sim f$. Maybe I have to use that $C*(n+1)$ is also a monotone function. I think I forgot something important out of the lectures Analysis I+II, which I have to use for a solution. Thanks for help.

  • 0
    Yes, but that's what I wrote: a counterexample *to* the inequality means the inequality doesn't hold.2011-11-14

1 Answers 1

1

To construct a counterexample to $f\le f$, we only need pairs of values that we can choose independently such that the inequality is violated at least once for each $C$. So, starting at $C=1$ with $n_1=1$, in each step choose $f(n_C)$ and $f(Cn_C+C)$ such that the inequality is violated for $C$. Then let $n_{C+1}=Cn_C+C+1$ and continue. Since the $n_C$ always increase, these are always new function values that can be chosen arbitrarily, and the remaining function values can also be chosen arbitrarily.

  • 0
    Thanks. Nice. I will ask my professor which conditions he forgot.2011-11-14