2
$\begingroup$

If $a_n = O(n^\alpha)$ and $b_n = o(n^\beta)$, prove that $a_nb_n = o(n^{(\alpha + \beta)})$ and $a_n+b_n = O(\max(n^\alpha, n^\beta))$.

For the part about $a_nb_n = o(n^{(\alpha + \beta)})$, I get that I am supposed to set it up so that

$|a_n| < Mn^\alpha$ for some positive real M for $n \geq n'$

$|b_n| < \epsilon n^\beta$ for all positive reals $\epsilon$ for $n \geq n''$

Then I choose the maximum of n' and n'', and I get

$|a_nb_n| < M\epsilon n^\alpha n^\beta$.

My question is does this finish the proof? If there is a positive real M multiplied by $\epsilon$, does that map to all $\epsilon$? How do you denote this? I think this is some real analysis proof here or I can just say a constant multiplied by epsilon is just epsilon?

For the sum proof, does it become big-O rather than little-O because it cannot be mapped to $\epsilon$ when you add the two parts?

Thank you in advance for the help.

$\endgroup$
3
  • $\begingroup$ For the second part, if $\beta > \alpha$ then you do get $o(n^\beta)$, but otherwise, all you can conclude is $O(n^\alpha)$. $\endgroup$ Nov 1 '20 at 19:16
  • $\begingroup$ Ok thank you, that makes sense. For the first part, is it valid to say something like $\epsilon$ times a constant will result in $\epsilon$? Like this is true from just logic, but I don't know if there's some math theorem I need to state. $\endgroup$
    – Alex
    Nov 1 '20 at 19:40
  • $\begingroup$ Use the definitions. That's all you need to know. $\endgroup$ Nov 1 '20 at 19:40
1
$\begingroup$

For $a_n$ you use correct definition i.e. $a_n \in O(n^\alpha)$: $\exists C>0, \exists N_1 \in \mathbb{N}, \forall n>N_1, |a_n| \leqslant C n^\alpha$.

For little-$o$ for $b_n \in o(n^\beta)$ let's use following definition : $\exists \varepsilon_n, \lim\limits_{n \to \infty}\varepsilon_n=0$ and $ \exists N_2 \in \mathbb{N}$ such that $ \forall n>N_2, b_n=\varepsilon_n n^\beta$.

So, taking $n>\max(N_1,N_2)$ we have $a_n \cdot b_n= \frac{a_n \varepsilon_n}{n^\alpha} \cdot n^{\alpha+\beta} = \phi_n n^{\alpha+\beta}$. We need to prove, that $\phi_n \to 0$: $|\phi_n| = |\frac{a_n \varepsilon_n}{n^\alpha}| \leqslant C |\varepsilon_n|\to 0$.

Hope you'll be able finish second using above.

$\endgroup$
2
  • $\begingroup$ Thanks I understand this. I have a small question. When you rewrote like the little-o notation, what happened to like the absolute value part of |bn|. In general, why is there an absolute value part for the definition of |an| to begin with? Furthermore, when you showed $\phi_n$ -> 0, you took the absolute value of it, but your definition of little-o didn't have the $\epsilon$ as an absolute value, so why do you need to consider the absolute value later. Thanks. $\endgroup$
    – Alex
    Nov 1 '20 at 22:48
  • $\begingroup$ In general definition of little-$o$ do not need absolute value. Estimation for absolute value is result of representation $b_n=\varepsilon_n n^\beta$. As to second question, then $\phi_n \to 0$ is same as $|\phi_n| \to 0$ and in latter we use estimation for absolute value for $a_n$. $\endgroup$
    – zkutch
    Nov 1 '20 at 23:04

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.