\documentclass[12pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\def\bparts{\begin{problemparts}}
\def\eparts{\end{problemparts}}
\def\ppart{\problempart}

\begin{document}
\inclassproblems{6F}

%F01, pset 7


% SOURCE SPRING 99 Q1
\begin{problem}
There is a number $a$ such that $\sum_{i=1}^\infty i^p$ converges iff $p <
a$.  What is the value of $a$?  Prove it.

\solution{$a= -1$.

For $p=-1$, the sum is the harmonic series which we know does not
converge.  Since the term $i^p$ is increasing in $p$ for $i>1$, the sum
will be larger, and hence also diverge for $p>-1$.

By the integral method, the sum is $\Theta$ of the integral from
1 to $\infty$ of $x^p$.  For $p<-1$, the indefinite integral is $x^{p+1}/(p+1) =
\Theta(1/x^\epsilon)$ for $\epsilon = -1 - p > 0$, so the integral
evaluates to a constant.  Hence the sum is bounded above, and since it is
increasing, it has a finite limit, \ie it converges.}

\end{problem}

\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}

\begin{problem}
Indicate which of the following holds for each pair of functions $(f(n),
g(n))$ in the table below.  Assume $k\geq 1$,
$\epsilon > 0$, and $c > 1$ are constants.
\begin{equation*}
\begin{array}{|cc|c|c|c|c|c|c|}
\hline
f(n) & g(n) & 
f = O(g) & f=o(g) & 
g = O(f) & g=o(f) & 
f = \Theta(g) & f\sim g 
\\\hline\hline
2^n & 2^{n/2} & & & & & & \\\hline
\sqrt{n} & n^{\sin n\pi/2} & & & & & & \\\hline
\log(n!) & \log(n^n) & & & & & & \\\hline
n^k & c^n & & & & & & \\\hline
\log^k n & n^\epsilon & & & & & & \\\hline
\end{array}
\end{equation*}

%\item $f=O(g)$
%\item $f=o(g)$
%\item $g=O(f)$
%\item $g=o(f)$
%\item $f = \Theta(g)$
%\item $f \sim g$
%\item none of the above.
%
%\begin{equation*}
%\begin{array}{|cc|}
%\hline
%f(n) & g(n) \\\hline\hline
%\log^k n & n^\epsilon \\\hline
%n^k & c^n \\\hline
%\sqrt{n} & n^{\sin n\pi/2} \\\hline
%2^n & 2^{n/2} \\\hline
%\log(n!) & \log(n^n) \\\hline
%\end{array}
%\end{equation*}

\solution{
\newcommand\y{\text{yes}}
\newcommand\n{\text{no}}
\[
\begin{array}{|cc|c|c|c|c|c|c|}
\hline
f(n) & g(n) & 
f = O(g) & f=o(g) & 
g = O(f) & g=o(f) & 
f = \Theta(g) & f\sim g 
\\\hline\hline
2^n & 2^{n/2} & 
\n & \n & \y & \y & \n & \n
\\\hline
\sqrt{n} & n^{\sin n\pi/2} & 
\n & \n & \n & \n & \n & \n
\\\hline
\log(n!) & \log(n^n) & 
\y & \n & \y & \n & \y &  \y
\\\hline
n^k & c^n &             
\y & \y & \n & \n & \n & \n
\\\hline
\log^k n & n^\epsilon & 
\y & \y & \n & \n & \n & \n
\\\hline
\end{array}
\]

Following are some hints on deriving the table above:

\begin{itemize}

\item[(a)] 
$\dfrac{2^n}{2^{n/2}}=2^{n/2}$ grows without bound as $n$
grows---it is not bounded by a constant.

\item[(b)] 
When $n$ is even, then $n^{\sin n\pi/2}=1$.  So, no constant times
$n^{\sin n\pi/2}$ will be an upper bound on $\sqrt n$ as $n$ ranges
over even numbers.  When $n \equiv 1 \bmod 4$, then $n^{\sin n\pi/2}=
n^1 =n$. So, no constant times $\sqrt n$ will be an upper bound on
$n^{\sin n\pi/2}$ as $n$ ranges over numbers $\equiv 1 \bmod 4$.

\item[(c)] 
\begin{eqnarray}
\log(n!) & = & \log \sqrt{2\pi n}\left(\frac{n}{e}\right)^n \pm
c_n\label{logS}\\
& = & \log n + n(\log n - 1) \pm d_n \label{logprod}\\
& \sim & n \log n\label{sim}\\
& = & \log n^n.
\end{eqnarray}
where $a \leq c_n,d_n \leq b$ for some constants $a,b \in \reals$ and all
$n$.  Here equation~(\ref{logS}) follows by taking logs of Stirling's
formula,~(\ref{logprod}) follows from the fact that the log of a product
is the sum of the logs, and~(\ref{sim}) follows from Problem~\ref{o+o},
part~\ref{f+o} because any constant, $\log n$, and $n$ are all $o(n \log
n)$.

\item[(d)] 
\emph{Polynomial} growth versus \emph{exponential} growth.

\item[(e)] 
\emph{Polylogarithmic} growth versus \emph{polynomial} growth. 

\end{itemize}

}
\end{problem}


% SOURCE:  FALL00, TUTORIAL 7
% TOPIC:  Asymptotic notation
% PSET?
\begin{problem} 
Given that $f(x) = O(g(x))$, prove or disprove the following: 
\begin{problemparts}

\problempart
$2^{f(x)} = O(2^{g(x)})$.

\solution{
The above does not hold. Let $f(x) = 2x$ and $g(x) = x$. Then $f(x)
= O(g(x))$. Now $2^{f(x)} = 2^{2x} = 4^x$, and $2^{g(x)} = 2^x$, and
$4^x\neq O(2^x)$. Indeed,
\[
\frac{4^x}{2^x} = 2^x,
\] so the ratio
grows without bound as $x$ grows---it is not bounded by a constant.
}

\problempart 
$f(x)^2 = O(g(x)^2)$.

\solution{%
The above does hold.  Since $f(x) = O(g(x))$, there exist $x_0$, $c$
such that for all $x \geq x_0$, $|f(x)| \leq c g(x)$.  So, for all 
$x\geq x_0$,  $|f(x)|^2 \leq c^2g(x)^2$.  Therefore, there exist 
$x_0' = x_0$ and $c' = c^2$ such that for all $x \geq x_0'$, 
$|f(x)^2| \leq c'g(x)^2$.  So $f(x)^2 = O(g(x)^2)$. 
}
\end{problemparts}
\end{problem}

% SOURCE:  FALL 00, TUTORIAL 7
% TOPIC:  Asymptotic notation
% in-class
\begin{problem}
Prove or give a counterexample:
If $f_1,f_2,\dots$ is a sequence of functions from $\naturals$ to
$\naturals$ such that $f_i(n) = O(1)$ for all $i\geq 1$, then 
\[
\sum_{i=1}^n f_i(n) = O(2^n).
\]

\solution{
False.  For a counterexample, pick $f_i$ to be the constant function 
\[
\text{for all $n$}:\quad f_i(n) = 4^i, 
\]
for all $i\geq 1$.  Then clearly for each $i$, we have $f_i = O(1)$.  But
\[
\sum_{i=1}^n f_i(n) \geq f_n(n) = 4^n,
\]
which is not $O(2^n)$.
}
\end{problem} 


\iffalse
\begin{problem}
Regrouping or reordering the terms of an infinite series is ok for
\emph{absolutely convergent} series, namely, series for which the sum of
the absolute values of their terms converges.

In other cases, rearranging terms is not ok.
An extreme example is
\[
S \eqdef \sum_{i=0}^{\infty} (-1)^i = 1 + (-1) + 1 + (-1) + \cdots
\]
because by regrouping the terms we can deduce:
\begin{eqnarray*}
S & = & [ 1 + (-1) ] + [ 1 + (-1) ] + \cdots = 0 + 0 + \cdots = 0,\\
S & = & 1 + [(-1) + 1] + [(-1) + 1] + \cdots = 1 + 0 + 0 + \cdots = 1.
\end{eqnarray*}

To see the problem here, let $S_n \eqdef \sum_{i=0}^{n}(-1)^i$.  Then $S_n
= 1$ for odd $n$ and $S_n = 0$ for even $n$.  Hence $S_n$ does not have a
well-defined limit as $n$ tends to infinity, implying that $S$ is not a
convergent series.

Even for convergent, but not absolutely convergent, series, rearranging
terms can cause big changes.  For example, the series
\[
1 - 1/2 + 1/3 - 1/4 \dots
\]
converges, but is not absolutely convergent.

Explain how to reorder terms in $1 - 1/2 + 1/3 - 1/4 \dots$, so that the
resulting series converges to 3.  \dots so it converges to 4.  \dots so it
doesn't converge.

\solution{
Note that the sum of the negative terms goes to negative infinity, because
the sum
\[
-1/2 - 1/4 - 1/6 -  \dots - 1/2n = -H_n/2 \sim (-\ln n)/ 2
\]
and $\ln n$ goes to infinity with $n$.  Similarly, the sum of the positive
terms goes to positive infinity.

To reorder the terms to converge to 3, begin by taking the positive terms
in decreasing order until their sum first exceeds 3.  Next, take the
negative terms in order of decreasing magnitude until the sum of all the
terms taken---positive and negative---first goes below 3.  Now take the
remaining positive terms in decreasing order until the sum again exceeds 3,
then the negative terms till the sum goes below 3, and so on.  It is always
possible to move the sum above or below 3 by taking enough of the remaining
positive or negative terms, because the remaining positive terms sum to
positive infinity and the remaining negative terms sum to negative
infinity.  Also, the running sum of the positive and negative terms taken
in this way goes above and below 3 at most by the magnitude of the last
term taken.  Since the magnitude of the terms goes to zero, this implies
that the sum goes above and below 3 by an amount that decreases to zero.
But this is exactly what it means to say the sum converges to 3.

Replacing ``3'' by ``4'' above yields an ordering in which the sum
converges to 4.

Finally, alternately taking enough positive terms to increase the sum by 1
and then taking one negative term, yields an ordering in which the sum
diverges to positive infinity.

This argument applies to \emph{any} convergent series that is not
absolutely convergent to show that it can be reordered to converge to
\emph{any} desired number, or to diverge.  The moral: when reordering terms
in a series, be sure to check for absolute convergence.

}
\end{problem}

%F01, tut7
\begin{problem}
Riemann's Zeta Function $\zeta(k)$ is defined to be the infinite
summation:
\[
1+\frac1{2^k}+\frac1{3^k} \cdots = \sum_{j \ge 1} \frac1{j^k}
\]
Below is a proof that 
\[
\sum_{k \ge 2} (\zeta(k)-1) = 1
\]
Justify each line of the proof.
\begin{eqnarray}
\sum_{k \ge 2} (\zeta(k)-1) %
& = & \sum_{k \ge 2} \left[ \left( \sum_{j \ge 1} \frac{1}{j^k} \right) - 1 \right] \label{eq:1} \\
& = & \sum_{k \ge 2} \sum_{j \ge 2} \frac{1}{j^k} \label{eq:2} \\
& = & \sum_{j \ge 2} \sum_{k \ge 2} \frac{1}{j^k} \label{eq:3} \\
& = & \sum_{j \ge 2} \frac{1}{j^2} \sum_{k \geq 0} \frac{1}{j^k} \label{eq:4} \\
& = & \sum_{j \ge 2} \frac{1}{j^2} \cdot \frac{1}{1 - 1/j} \label{eq:5} \\
& = & \sum_{j \ge 2} \frac{1}{j (j - 1)} \label{eq:6} \\
& = & \lim_{n \rightarrow \infty} \sum_{j = 2}^{n} \frac{1}{j (j - 1)} \label{eq:7} \\
& = & \lim_{n \rightarrow \infty} \sum_{j = 2}^{n} \frac{1}{j-1} -\frac{1}{j} \label{eq:8} \\
& = & \lim_{n \rightarrow \infty} (1 - \frac{1}{n}) \label{eq:9} \\
& = & 1 \label{eq:10} 
\end{eqnarray}

\solution{
\eqref{eq:1}~Definition of $\zeta(k)$.
\eqref{eq:2}~Because ${\displaystyle \sum_{j \ge 1} \cfrac{1}{j^k} = 1 + \sum_{j \ge 2} \cfrac{1}{j^k}}$.
\eqref{eq:3}~Reordering; this is ok because at this point all terms are positive.
\eqref{eq:4}~Because 
$\displaystyle
\sum_{k \ge 2} \cfrac{1}{j^k} = 
\sum_{k \ge 0} \cfrac{1}{j^{k+2}} = 
\sum_{k \ge 0} \cfrac{1}{j^k\cdot j^2} =
\cfrac{1}{j^2} \sum_{k \ge 0} \cfrac{1}{j^k}
$.
\eqref{eq:5}~Theorem~2.2 from Notes~\#7.
\eqref{eq:6}~Algebra inside every summand.
\eqref{eq:7}~Definition of infinite summation.
\eqref{eq:8}~Algebra inside every summand.
\eqref{eq:9}~The sum telescopes: 1 is added once; every one of 
$\cfrac{1}{2}, \cfrac{1}{3}, \dots, \cfrac{1}{n-1}$ is subtracted once
and then added once; $\cfrac{1}{n}$ is subtracted once.
\eqref{eq:10}~Simple limits.
}
\end{problem}

\fi
\ifshowsolutions
{}
\else

\appendix
\section{Asymptotic Notations}

\begin{definition}
For functions $f,g: \reals \to \reals$, we say $f$ is \emph{asymptotically
equal} to $g$, in symbols,
\[
f(x) \sim g(x)
\]
iff
\[
\lim_{x \rightarrow \infty} f(x)/g(x) = 1.
\]
\end{definition}

\begin{definition}
For functions $f,g: \reals \to \reals$, we say $f$ is \emph{asymptotically
smaller} than $g$, in symbols,
\[
f(x) = o(g(x)),
\]
iff
\[
\lim_{x \rightarrow \infty} f(x)/g(x) = 0.
\]
\end{definition}

\begin{definition}[Using Limits]
Given functions $f, g : \reals \mapsto \reals$, with $g$ nonnegative, we
say that\footnote{
\[
\limsup_{x \rightarrow \infty} h(x) \eqdef \lim_{x \rightarrow \infty}
\text{lub}_{y \geq x} h(y).
\]}
\[
f = O(g)
\]
iff
\[
\limsup_{x \rightarrow \infty} \abs{f(x)}/g(x) < \infty.
\]
\end{definition}

\begin{definition}[Standard]
Given functions $f, g : \reals \mapsto \reals$, we say that
\[
f = O(g)
\]
iff there exists a constant $c \geq 0$ and an $x_0$ such that for all $x \geq
x_0$, $\abs{f(x)} \leq c g(x)$.
\end{definition}

\begin{definition}
\[
f = \Theta(g) 
\quad\text{iff}\quad  
f=O(g) \land g=O(f).
\]
\end{definition}
\newpage

\fi 

\end{document}
