0
$\begingroup$

Suppose $f_1 \in O(g)$ and $f_2 \in O(g)$, and $s$ and $t$ are real numbers. Define a function $f: \mathbb Z^{+} \rightarrow \mathbb R$ by the formula $f(x) = sf_1(x) + tf_2(x)$. Prove that $f \in O(g)$.

Definition of $O(g)$:

$F = \{f \mid f : \mathbb Z^+ \rightarrow \mathbb R\}$. For $g \in F$, we have

$$O(g) = \{f \in F \mid \exists a \in \mathbb Z^+ \exists c \in \mathbb R^+ \forall x > a (|f(x)| ≤ c|g(x)|)\}$$

My attempt:

Suppose there exist arbitrary functions $f_1$, $f_2$ such that both are in $O(g)$.

Since $f_1 \in O(g)$, exists $c_1$ and $a_1$ such that for all $x > a_1$:

$$|f_1(x)| ≤ c_1|g(x)|$$

And since $f_2 \in O(g)$, exists $c_2$ and $a_2$ such that for all $x > a_2$:

$$|f_2(x)| ≤ c_2|g(x)|$$

Take $k > a_1$ and $k > a_2$. We know that for all $x > k$

$$|f_1(x)| ≤ c_1|g(x)|$$

and

$$|f_2(x)| ≤ c_2|g(x)|$$

Let's take arbitrary $s$ and $t$. We need to consider three cases:

  1. $s$ and $t$ are both positive or zero

  2. $s$ and $t$ are both negative

  3. One is positive or zero, one is negative.

1.

Since both $≥ 0$, we have

$$s|f_1(x)| ≤ sc_1|g(x)|$$

$s|f_1(x)| = |sf_1(x)|$, thus we can rewrite inequality above as

$$|sf_1(x)| ≤ sc_1|g(x)|$$

By the same token, we have $$|tf_2(x)| ≤ tc_2|g(x)|$$

Adding both inequalities gives

$$|sf_1(x)| + |tf_2(x)| ≤ (sc_1 + tc_2)|g(x)|$$

By triangle inequality we conclude that

$$|sf_1(x) + tf_2(x)| ≤ (sc_1 + tc_2)|g(x)|$$

2.

Since $s$ and $t$ are both negative, we have

$$s|f_1(x)| ≥ sc_1|g(x)|$$ $$t|f_2(x)| ≥ tc_2|g(x)|$$

Both can be rewritten as

$$-|sf_1(x)| ≥ sc_1|g(x)|$$ $$-|tf_2(x)| ≥ tc_2|g(x)|$$

Multiplying both sides by $-1$ $$|sf_1(x)| ≤ -sc_1|g(x)|$$

$$|tf_2(x)| ≤ -tc_2|g(x)|$$

Adding them together gives

$$|sf_1(x)| + |tf_2(x)| ≤ -(sc_1 + tc_2)|g(x)|$$

By triangle inequality we have our result

$$|sf_1(x) + tf_2(x)| ≤ -(sc_1 + tc_2)|g(x)|$$

3.

Suppose $s ≥ 0$ and $t < 0$. We have

$$|sf_1(x)| ≤ sc_1|g(x)|$$

and

$$t|f_2(x)| ≥ tc_2|g(x)| \implies $$ $$-|tf_2(x)| ≥ tc_2|g(x)| \implies $$ $$|tf_2(x)| ≤ -tc_2|g(x)|$$

Adding them together gives

$$|sf_1(x)| + |tf_2(x)| ≤ (sc_1 - tc_2)|g(x)|$$

And by triangle inequality we have our result $$|sf_1(x) + tf_2(x)| ≤ (sc_1 - tc_2)|g(x)|$$

Case where $s < 0$ and $t ≥ 0$ is nearly identical to the one we've just shown.

Hence for arbitrary $s$ and $t$, there will exist some positive scalar $c$ such that for all $x > k$

$$|f(x)| ≤ c|g(x)|$$

Hence $f \in O(g)$

Is it correct?

$\endgroup$
3
+25
$\begingroup$

I didn't read through your entire proof, but I have no doubt that it can be done by breaking it into cases. However, why bother when you can immediately use the triangle inequality and the fact that $|xy|=|x|\cdot |y|$ to get $$\begin{aligned} |sf_1(x)+tf_2(x)| &\le |s|\cdot |f_1(x)|+|t|\cdot|f_2(x)| \\ &\le (|s|c_1+|t|c_2)\,|g(x)| \end{aligned}$$ for sufficiently large $x$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.