-1

eventually dominated(ed) $\exists m \in \mathbb{R}_{\ge 0}: \forall n \in \mathbb{N}, n \ge m \Rightarrow g(n) \leq f(n)$

$\forall x, y \in \mathbb{R}_{\ge 0}, g(n) = xn + y$ is (ed) by $f(n) = n^2$

Should translate to.. $\forall x,y\in\mathbb{R}_{\ge 0},\exists m \in \mathbb{R}_{\ge 0}: \forall n \in \mathbb{N}, n\ge m \Rightarrow xn+y \leq n^2$

So I understand this can be done with the quadratic fomula by finding the intersection which will be the "best" m but I only need to find an $m$ that works so I am not required to use the quadratic formula. So how do you go about proving this without the quadratic formula and the intersection etc. Just some logical chain or maybe induction?

thanks

John
  • 1,019
shibu
  • 57
  • 7
  • Your objective here seems muddled. You know how to get an explicit answer using the quadratic formula to find $m$, but you want to do it another way. But would you be satisfied by an approach that proves "eventually dominated" in a non-constructive fashion? This is related to showing an upper bound on a set (rather than a least upper bound). – hardmath Feb 15 '17 at 13:55
  • yes...do you know some other way besides what quas did? – shibu Feb 15 '17 at 16:28

1 Answers1

0

Fix $\,x,y \in \mathbb{R},\;x,y \ge 0\,$.

Choose $m \in \mathbb{R}$ such that

$\qquad (1)\;\;\,\,\, m \ge 2x$

$\qquad (2)\;\;\,m^2 \ge 2y$

Then for all $n \ge m$,

$\qquad\;\;\;\;\;\, 2n^2 = n^2 + n^2$

$\qquad\qquad\;\;\;\;\; \ge mn + m^2$

$\qquad\qquad\;\;\;\;\; \ge (2x)n + (2y)$

$\qquad\qquad\;\;\;\;\; = 2(xn + y)$

Hence

$\qquad\;\;\;\;\;\, n^2 \ge xn + y$

as required.

quasi
  • 58,772