0

Let $F=\{f \; \vert f:\mathbb{Z}^+\rightarrow\mathbb{R}\}$, $O(g)=\{f\in F|\exists a\in\mathbb{Z}^+\exists c\in\mathbb{R}^+\forall x>a(|f(x)|\le c|g(x)|)\}$
$f(x)=7x+3$ and $g(x)=x^2$.

Prove $f\in O(g)$ but $g\not \in O(f)$.

I dont know what kind of scratch work I should be doing here, I'm more used to doing proofs regarding sets and relations and stuff like that, not with equations.

I started by listing $f(x)$ and $g(x)$ and incrementing $x$ every time. I found out that when $x\ge 8$, then $f(x)\le g(x)$ (not 100% sure this is correct). So should I then let $a=8$ and $c=1$?

But how do I proceed from here? The correct solution uses $a=3$ and $c=8$, but I dont understand why, and I'd like to understand what kind of scratch work should be done to come to that conclusion.

Digitallis
  • 3,780
  • 1
  • 9
  • 31
lightyourassonfire
  • 333
  • 7
  • When you find one pair $a,c$, then you can find infinite - simply increase each. So "correct" should use some additional requirement. For example find minimal $a$ ect. More interesting is negation. – zkutch Jun 17 '23 at 12:01
  • but how do I find those $a$ and $c$? There must be a better way than just listing $f(x)$ and $g(x)$ for different values of $c$ and $a$ – lightyourassonfire Jun 17 '23 at 12:09

1 Answers1

0

As I wrote in comment definition brings us to inequality $$7x+3\leqslant c\cdot x^2$$ When we want "tight" estimation, then we should study relations between parabola $c\cdot x^2$ and straight line $7x+3$. enter image description here

As you see from picture, the more $c$ we choose, then the less will be right intersection point. One most easy way is to estimate from right: $7x+3 \leqslant 7x^2+3x^2=10 x^2$, so we find such $c=10$ for which works $a=1$. Generally answer gives any correctly found pair.

Now to obtain $g\notin O(f)$ we should write firstly formal negation $$(\forall a\in\mathbb{Z}^+)(\forall c\in\mathbb{R}^+)(\exists x>a)(|g(x)|>c|f(x)|)\}$$ essential difference here is, that now you have $2$ variables under universal quantifier, so, $2$ are given and $1$ we should find. Our inequality becomes

$$x^2 > c\cdot (7x+3)$$ Let's use following estimation $7x+3<10x$, when $x>1$, so it is enough to solve inequality $$x^2 > c\cdot 10x$$ for $x>1$ it becomes $$x > c\cdot 10$$ so for any given $c>0$ and any given $a$ if we choose $x>\max(1, 10c, a)$, then negation will be proved.

zkutch
  • 13,410
  • what is that application/website in the screenshot? – lightyourassonfire Jun 17 '23 at 12:28
  • https://www.desmos.com/calculator – zkutch Jun 17 '23 at 12:31
  • how did you come up with $7x+3<10x$? – lightyourassonfire Jun 17 '23 at 13:18
  • This is an estimate - a simplification by which I reduced the problem to an easier one. You can find, of course, other ways - I found this one. – zkutch Jun 17 '23 at 13:23
  • but how did you find it? What kind of scratch work did you do for this proof before finding the solution? Did you use the graphing tool for this one aswell? – lightyourassonfire Jun 17 '23 at 13:25
  • I wanted to simplify $x^2 > c\cdot (7x+3)$. So, I see $2$ ways: or decrease left side or increase right one. I found simpler latter. – zkutch Jun 17 '23 at 13:27
  • how can you infer $x^2>c10x$? If $x=10$, then $1010>c1010$, i dont see how this is valid since $c$ is arbitrary – lightyourassonfire Jun 17 '23 at 13:30
  • If sentence is right for $x^2 > c\cdot 10x$, then it will be right also for $x^2 > c\cdot (7x+3)$, because $c\cdot10x > c\cdot (7x+3)$. And for final conclusion look at the last sentence in answer - I wrote condition $x>\max(1, 10c, a)$, by which for any $c,a$ we can find correct $x$. – zkutch Jun 17 '23 at 13:34
  • but how do you know its right for $x^2>c*10x$? In my opinion you have assumed $7x+3<10x$ and then derived $x^2>c(10x)$ – lightyourassonfire Jun 17 '23 at 13:38
  • No. It is not assumption. I wrote: $7x+3<10x$, when $x>1$. It is true implication. And this true sentence I used as show in answer and previous comment. This $x>1$ is used in $x>\max(1, 10c, a)$, in last sentence. – zkutch Jun 17 '23 at 13:41
  • did the graph help you when solving this problem? I found the graph helpful in the first proof, but idk how to use it in this second proof – lightyourassonfire Jun 17 '23 at 13:53
  • Basically you are right. Figures are more helpful in proving the definition, maybe, less in negation. In any case, the drawing only suggests the direction of thinking. Having the drawing and the idea of the proof, the most difficult thing remains: to construct the formal proof itself. – zkutch Jun 17 '23 at 13:56