\documentclass[11pt,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}
{\href{http://theory.lcs.mit.edu/~meyer}{Prof.~Albert~R.~Meyer}}


\begin{document}
\inclassproblems{7, Fri}

%S02 cp6F

%F01, pset 7

\instatements{\section{Problems}}

% 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$.}

\iffalse

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

\solution{
\iffalse
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. -- ARM
\fi

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}
\]
\ie $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
\]
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 (mean), of the variables.
\begin{proof} (of lemma)
\begin{align*}
\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{align*}
\end{proof}
}
\fi

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

\iffalse

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



% SOURCE:  FALL 00, TUTORIAL 7
% TOPIC:  Asymptotic notation
% in-class  SUBSTANTIALLY REVISED, F02 -- ARM

\begin{problem}
It is a standard fallacy to think that given $n$ quantities each of which
is $O(1)$, their sum would have to be $O(n)$.  In fact, such a sum can
grow arbitrarily fast:

Let $g:\naturals \to \naturals^{+}$ be \emph{any} function.  Explain how
to define a sequence $f_1,f_2,\dots$ of functions from $\naturals$ to
$\naturals$ such that
\begin{equation}\label{fO1}
f_i(n) = O(1)
\end{equation}
for all $i\geq 1$, but
\begin{equation}\label{nO}
\sum_{i=1}^n f_i(n) \neq  O(g(n)).
\end{equation}

\solution{
Pick $f_i$ to be the constant function $ig(i)$.  That is,
\[
f_i(n) \eqdef ig(i),
\]
for all $i\geq 1$ and $n \ge 0$.  Since $f_i$ is a constant function, it
is $O(1)$, that is, condition~(\ref{fO1}) holds.

But
\[
\sum_{i=1}^n f_i(n) \geq f_n(n) = ng(n),
\]
and $ng(n) \neq O(g(n))$, so~(\ref{nO}) also holds.  In fact, since $g(n) =
o(ng(n))$, we have the stronger condition that
\[
g(n) = o\left(\sum_{i=1}^n f_i(n)\right).
\]
}

\end{problem} 


\iffalse

%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

\instatements{
\section{Appendix: 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}
}
 

\end{document}
