As part of a problem i am solving i am required to prove th Suppose $f_1\in O(g)$ and $f_2\in O(g)$, and $s$ and $t$ are real numbers. Define a function $f:\mathbf{Z^+}\rightarrow \mathbf{R}$ by the formula $f(x) = sf_1(x) + tf_2(x)$, then $f\in O(g)$

where $O(g) = \{f\in\mathcal{F}|\exists a\in\mathbf{Z^{+}}\exists c\in\mathbf{R^{+}}\forall x>a(|f(x)|\leq c|g(x)|)\}$ and $\mathcal{F}=\{f|f:\mathbf{Z^{+}}\rightarrow\mathbf{R}\}$

Proof. Assume that $f_1\in O(g)$, $f_2\in O(g)$, $s\in\mathbf{R}$ and $t\in\mathbf{R}$, it then follows that for some $a_1\in \mathbf{Z^+}$, $a_2\in \mathbf{Z^+}$,$c_1\in \mathbf{R^+}$ and $c_2\in \mathbf{R^+}$, it is the case that $\forall x>a_1(|(f_1(x)|\leq c_1|g(x)|$ and $\forall x>a_2(|(f_2(x)|\leq c_2|g(x)|$, arguing from cases.

Case-1$(a_1<a_2)$: Assume that $a_1<a_2$, let $\alpha = a_2$ and $\beta = c_1|s|+c_2|t|$. Consider an arbitrary $x>a_2$ it is evident that $|(f_1(x)|\leq c_1|g(x)|$ and that $|(f_2(x)|\leq c_2|g(x)|$, but this implies that $|s||(f_1(x)|= |s(f_1(x)|\leq c_1|s||g(x)|$ and $|t||(f_2(x)|= |t(f_2(x)|\leq c_2|t||g(x)|$, taking these two inequalities together $|s(f_1(x)|+|t(f_2(x)|\leq c_1|s||g(x)|+|t(f_2(x)|\leq c_1|s||g(x)|+c_2|t||g(x)|$ thus $|s(f_1(x)|+|t(f_2(x)|\leq c_1|s||g(x)|+c_2|t||g(x)|$, but use of the triangle inequality suggests that $|s(f_1(x)+t(f_2(x)|\leq |s(f_1(x)|+|t(f_2(x)|$ allowing us to conclude that $|s(f_1(x)+t(f_2(x)|\leq c_1|s||g(x)|+c_2|t||g(x)|= (c_1|s|+c_2|t|)(|g(x)|)$.

We may now conclude that $\forall x>\alpha(|f(x)|\leq \beta|g(x)|)$ implying that $f\in O(g)$.

Case-2$(a_2<a_1)$: The proof is similar to Case-1.

Case-3$(a_1=a_2)$: The proof is similar to Case-1.


Is the above proof correct, and any suggestions for improving the write-up would be much appreciated.

  • $\begingroup$ Look at the definition of $O(g)$ : why are its elements couples of functions $(f,g)$ ? $\endgroup$ – Max Jun 23 '17 at 21:41
  • $\begingroup$ apologies problem has been corrected $\endgroup$ – Atif Farooq Jun 23 '17 at 21:50
  • $\begingroup$ Well now the proof is fine, only you really don't need to argue by cases, simply put $a > max(a_1, a_2)$ $\endgroup$ – Max Jun 24 '17 at 7:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.