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$

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .