\problemdata      
        {asymptotics-1} % latex-friendly label for the prob.
        {Asymptotics} % The topic(s) of the problem content.
        {?} % Source (if known)
        {S02 CP6F} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).




\begin{problem}\label{o+o}
Suppose $f_1,f_2,g_1,g_2:\naturals \to \naturals$.  Prove the following:

\bparts

\ppart\label{f+o} If $f_1 = o(g_1)$, then $f_1+g_1 \sim g_1$.

\solution{
\[
\lim_{n \to \infty}\frac{f_1+g_1}{g_1} = \lim_{n \to
\infty}\frac{f_1}{g_1}+ \frac{g_1}{g_1} = 0 + 1 = 1.
\]
}
\ppart If $f_1 = o(g_1)$ and $f_2 = o(g_2)$, then $f_1 + f_2 = o(g_1 +
g_2)$.
\solution{
\begin{eqnarray}
\lim_{n \to \infty} \frac{f_1+f_2}{g_1+g_2}
           &=& \lim_{n \to \infty} \frac{f_1+f_2}{g_1+g_2}\\
 & = & \lim_{n \to \infty} \frac{f_1}{g_1+g_2} + \frac{f_2}{g_1+g_2}\\
 & \leq & \lim_{n \to \infty} \frac{f_1}{g_1} + \frac{f_2}{g_2}\\
 & = & \lim_{n \to \infty} \frac{f_1}{g_1} + \lim_{n \to \infty}\frac{f_2}{g_2}\\
 & = & 0+0 = 0.
\end{eqnarray}}

\ppart If $f_1 = O(g_1)$ and $f_2 = O(g_2)$, then $f_1 + f_2 = O(g_1 +
g_2)$.

\solution{
Say $f_1(n) \leq c_1 g_1(n)$ and $f_2(n) \leq c_2 g_2(n)$ for some
constants $c_1,c_2 \geq 0$ and all large $n$.  Then
\[
f_1(n) + f_2(n) \leq c_1 g_1(n) + c_2 g_2(n) \leq c (g_1(n) + g_2(n)),
\]
where $c = \max{c_1,c_2}$.
}

\ppart If $f_1 \sim g_1$ and $f_1 \geq f_2 \sim g_2 \leq g_1$, then it is
\emph{not} necessarily true that $f_1 - f_2 \sim g_1 - g_2$.

\solution{Let $f_1 \eqdef n+1, g_1 \eqdef n + 2, f_2 \eqdef g_2 \eqdef n$.}

\ppart If $f_1 \sim g_1$ and $f_2  \sim g_2$, then $f_1 + f_2  \sim g_1 +
g_2$.

\solution{
%I have a couple of proofs, neither of them as slick as I'd like.  Maybe
%some students or TA's will find a nicer one---if we actually get to
 %this problem.
Let $r_1 = f_1/g_1, r_2 = f_2/g_2, r=(f_1+f_2)/(g_1+g_2)$.  Then
$$
r = \frac{g_1 r_1 + g_2 r_2} {g_1+g_2}
$$
i.e. $r$ is the weighted average of $r_1$ and $r_2$, where $g_1$ and
$g_2$ are the weights.  Applying the useful lemma below, we see that
$r$ must always lie between $r_1$ and $r_2$.  Since $r_1$ and $r_2$
converge to 1 as $n$ goes to $\infty$, so must $r$.  This implies $f_1
+ f_2  \sim g_1 +g_2$ as desired.
\begin{lemma*}
For any sequence $x_1, x_2... x_m$ of reals, and any sequence
$w_1, w_2... w_m$ of nonnegative reals,
$$
\min_i x_i\leq\frac{\sum_j w_jx_j}{\sum_j w_j}\leq\max_i x_i
%\min_i x_i=\frac{\sum_i w_i}{\sum_i w_i}\min_i x_i=\leq\frac{\sum_i w_i\min_j x_j}{\sum_i w_i}\leq\frac{\sum_i w_ix_i}{\sum_i w_i}\leq\max_i x_i
$$
with equality holding iff all the $x_i$'s are equal.
\end{lemma*}
The central fraction is called the {\bf weighted average}, where the
$x_j$'s are the variable being averaged and the $w_i$'s are the
weights.  
Clearly if all the $w_i$'s are set equal to 1 then this
simplifies to the standard average, or the mean of the variables.
\begin{proof} (of lemma)
$$
\min_i x_i=\frac{\sum_j w_j}{\sum_j w_j}\min_i x_i=\frac{\sum_j
  w_j\min_i x_i}{\sum_j w_j}\leq\frac{\sum_j w_jx_j}{\sum_j w_j}
$$$$
\max_i x_i=\frac{\sum_j w_j}{\sum_j w_j}\max_i x_i=\frac{\sum_j
  w_j\max_i x_i}{\sum_j w_j}\geq\frac{\sum_j w_jx_j}{\sum_j w_j}
$$
\end{proof}
}

\eparts
\end{problem}
