\documentclass[11pt,twoside]{article}   
\usepackage{latex-macros/course}

\renewcommand{\reading}
{\href{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln6.pdf}
{Week 6 Notes}, Optional: Rosen \S 3.3;
\href{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln7.pdf}
{Week 7 Notes}, Optional: Rosen \S 1.7--8.}

%\hidesolutions         
%\showsolutions

\newcommand{\rt}{\text{root}}
\newcommand{\PT}{\text{PayT}}

\newcommand{\lub}{\text{lub}}
\newcommand{\glb}{\text{glb}}

\newcommand{\mav}{\text{max-value}}
\newcommand{\miv}{\text{min-value}}
\newcommand{\subtrees}{\mathcal{S}}



\begin{document}
\problemset{6-7}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}

We can generalize win-lose 2-player terminating games of perfect
information to games with ``payoff'' amounts.  In these games, two players
called the \emph{max-player} and the \emph{min-player} alternate moves
until the game ends with the min-player paying some payoff amount to the
max-player.  How much the min-player pays depends on how the game ends.
Negative payoffs mean the max-player pays the min-player.  The max-player
moves first.

Such games are defined by finite-path trees with leaves labelled with real
numbers.  These are the payoff amounts.  The max-player tries to arrive at
a leaf with as large a payoff as possible, and the min-player tries to
minimize the payoff to the max-player.

\begin{definition*}

The set of payoff-game trees, $\PT$, can be defined recursively as
follows:
\begin{enumerate}

\item If $T$ is a graph with one vertex, $v$, and no edges, then $T$ is a
$\PT$ and $\rt(T) \eqdef v$.

\item If $\subtrees$ is a set of $\PT$'s such that no vertex occurs in
more than one tree in $\subtrees$, and $v$ is a ``new'' element that is
not a vertex of any tree in $\subtrees$, then $T$ is in $\PT$ where
$\rt(T) = v$ and the edges of $T$ are the edges of all the trees in
$\subtrees$ along with edges connecting $\rt(T)$ to the roots of each of
the trees in $\subtrees$.  The trees in $\subtrees$ are called the
\emph{children} of $T$.

\end{enumerate}

\end{definition*}

We define functions $\mav(T)$ and $\miv(T)$ on payoff-game trees, $T \in
\PT$, recursively on the definition of $\PT$:

\begin{enumerate}

\item If $T$ is a single node labelled $r$, then
\[
\mav(T) = \miv(T) \eqdef r.
\]

\item If the nonempty set, $\subtrees$, is the set of children of $T$,
then\footnote{$\glb = \text{``greatest-lower-bound''}$ and
$\lub = \text{``least-upper-bound''}$, \cf Rosen, p. 423.}

\begin{eqnarray*}
\mav(T) & \eqdef & \lub \set{\miv(S) \suchthat S \in \subtrees}\\
\miv(T) & \eqdef & \glb \set{\mav(S) \suchthat S \in \subtrees}.
\end{eqnarray*}

\end{enumerate}

\bparts

\ppart Suppose a payoff-game tree, $T$, is \emph{finite}.  Prove that
\begin{enumerate}

\item \label{max-first} If the max-player is the first player to move in
$T$, then he has a strategy that guarantees his payoff will be at least
$\mav(T)$, no matter how the min-player behaves.

\item \label{max-second} If the max-player is the second player to move in
$T$, then he has a strategy that guarantees his payoff will be at least
$\miv(T)$.

\item \label{min-first} Likewise, if the min-player is the first player to
move in $T$, then she has a strategy that guarantees the payoff to
max-player will be at most $\miv(T)$.

\item \label{min-second} If the min-player is the second player to move in
$T$, then she has a strategy that guarantees the payoff to max-player will
be at most $\mav(T)$.

\end{enumerate}
(So the players may as well skip playing and just have the min-player pay
$\mav(T)$ to the max-player.)

\solution{
The max-player's strategy is to move on his turn to the subtree with the
largest $\miv$.  The min-player's strategy is to move to the subtree with
the smallest $\mav$.

By structural induction on the definition of $\mav(T)$ and $\miv(T)$, we
prove~\ref{max-first}.\ and~\ref{max-second}.

\textbf{Base case} ($T$ is a leaf): The game is over with no moves, and
the max-player's payoff is the payoff at the the leaf.  This is $\mav(T)$
by definition of $\mav$.

\textbf{Induction case:} ($T$ has a nonempty set, $\mathcal{S}$, of
(direct) subtrees)

Suppose the max-player moves first in $T$.  Using his strategy, he moves
to $S \in \subtrees$ with the largest $\miv$.  Now in the game defined by
$S$, he moves second.  By induction hypothesis~\ref{max-second}., he has a
strategy in $S$ guaranteeing at payoff at least $\miv(S)$.  Hence, he is
guaranteed a payoff of at least $\max \set{\miv{S} \suchthat S \in
\subtrees}$.  But by definition, this is precisely $\mav(T)$.

A corresponding proof using induction hypothesis~~\ref{max-first} shows
his strategy ensures payoff at least $\miv(T)$ if he moves second in $T$.
A similar proof confirms~\ref{min-first}.\ and ~\ref{min-second}.}

\ppart Now generalize the previous part to arbitrary $\PT$'s.  \hint It
might be helpful to assume the payoff amounts at the leaves are bounded
above and below by particular numbers.  After settling this case, try it
without assuming bounds.  Note that in the unbounded case, $\mav(T)$ may
be $+\infty$ and $\miv(T)$ may be $-\infty$.

\solution{
In the bounded case, we can say that for any $\epsilon >0$,

\begin{enumerate}

\item the max-player has a strategy that guarantees his payoff will be
\emph{at least} $\mav(T)-\epsilon$,

\item the min-player has a strategy that guarantees the max-player's
payoff will be \emph{at most} $\mav(T) + \epsilon$.

\end{enumerate}

The max-player's strategy is to move on his turn to a subtree, $S_0$, with
\[
\miv(S_0) \ge \lub \set{\miv(S) \suchthat S \in \subtrees} - \epsilon/2,
\]
and then to use his strategy in $S_0$ to guarantee a payoff $\ge \miv(S) -
\epsilon/2$.

The min-player's strategy is to move on his turn to a subtree, $S_1$, with
\[
\mav(S_1) \le \glb \set{\mav(S) \suchthat S \in \subtrees} + \epsilon/2,
\]
and then to use his strategy in $S_1$ to guarantee a payoff $\le \mav(S) +
\epsilon/2$.

The rest of the proof by structural induction is essentially the same as
for the finite case.

In the unbounded case, it may be, for example, that $\mav(T) = \infty$.  In
this case, the generalization of part~(a) is that for \emph{any} real
number, $r$, the max-player has a strategy that guarantees him a payoff of
at least $r$.  We omit the details.}

\eparts
\end{problem}


\begin{problem}
Week 6 Notes describes various functional equations, some of which serve
as function definitions because there is only one function satisfying the
equations, others of which are \emph{ambiguous} because more than one
function satisfies the equations, and some of which are
\emph{inconsistent} and aren't satisfied by any function at all.  It can
be hard to tell which case applies.  In this problem, we'll consider some
odd-ball equations which \emph{do} turn out to define a function uniquely,
though it's not obvious from the form of the equations that this is the case.

Suppose a function $f:\naturals \to \naturals$ satisfies the following equations:
\begin{align}
f(n) & = n - 3 & \text{ for } n \geq 10000, \label{f>=10}\\
f(n) & = f(f(n+5)) & \text{ for } n < 10000.\label{f<10}
\end{align}

\begin{problemparts}
\problempart
\label{example}

What must the values of $f(n)$ be for $n$ = 9996, 9997, 9998, 9999, and
10000?

\solution{
\begin{eqnarray*}
f(9996) &=& 9997\\
f(9997) &=& 9998\\
f(9998) &=& 9997\\
f(9999) &=& 9998\\
f(10000) &=& 9997.
\end{eqnarray*}
}

\problempart\label{simpledef}

Prove that there is a function satisfying equations~(\ref{f>=10})
and~(\ref{f<10}) by giving a simple, explicit definition for such an $f$
and proving that the function you defined satisfies~(\ref{f>=10})
and~(\ref{f<10}).

%Hint: You may want to try more numbers close to 10000.

\solution{
Let
\begin{align}
f_0(n) \eqdef& n - 3 & \text{ when } n \geq 10000,\label{n-3}\\
f_0(n) \eqdef& 9997 & \text { when } n \text{ is even and } n < 10000,\label{even}\\
f_0(n) \eqdef& 9998 & \text { when } n \text{ is odd and } n < 10000.\label{odd}
\end{align}

We need to show that $f_0$ satisfies equations~(\ref{f>=10})
and~(\ref{f<10}).

Now $f_0$ clearly satisfies~(\ref{f>=10}), since equation~(\ref{n-3}) in the
definition of $f_0$ is the same as~(\ref{f>=10}).

It remains to show that $f_0$ satisfies~(\ref{f<10}), namely, that
\begin{equation}
f_0(n) = f_0(f_0(n+5))\label{f0f}
\end{equation}
for $n<10,000$.

First, consider $n < 9995$ so that $n+5 < 10000$. 

\begin{description}

\item[Case 1:] $n$ is odd. Then

\begin{align*}
f_0(n) & = 9998 & \text{by~(\ref{odd})}\\
       & = f_0(9997) & \text{by~(\ref{odd})}\\
       & = f_0(f_0(n+5)) & \text{by~(\ref{even}) because $n+5$ is even}.
\end{align*}

\item[Case 2:] $n$ is even.  Then
\begin{align*}
f_0(n) & = 9997 & \text{by~(\ref{even})}\\
       & = f_0(9998) & \text{by~(\ref{even})}\\
       & = f_0(f_0(n+5)) & \text{by~(\ref{odd}) because $n+5$ is odd}.
\end{align*}

\end{description}

So it remains only to check~(\ref{f0f}) for $9995 \le n < 10000$.  In
particular, for $n=9995$ we have
\begin{align*}
f_0(9995) & = 9998 & \text{by~(\ref{odd})}\\
          & = f_0(9997) & \text{by~(\ref{odd})}\\
          & = f_0(f_0(10000)) & \text{by~(\ref{n-3})}\\
          & = f_0(f_0(9995-5)).
\end{align*}

For $n=9996$ we have
\begin{align*}
f_0(9996) & = 9997 & \text{by~(\ref{even})}\\
          & = f_0(9998) & \text{by~(\ref{even})}\\
          & = f_0(f_0(10001)) & \text{by~(\ref{n-3})}\\
          & = f_0(f_0(9996+5)).
\end{align*}

The arguments for $n=9997, 9998$ are essentially the same.  Finally,
for $n=9999$ we have
\begin{align*}
f_0(9999) & = 9998 & \text{by~(\ref{odd})}\\
          & = f_0(10001) & \text{by~(\ref{n-3})}\\
          & = f_0(f_0(10004)) & \text{by~(\ref{n-3})}\\
          & = f_0(f_0(9999+5)).
\end{align*}
}

\problempart Prove that equations~(\ref{f>=10}) and~(\ref{f<10})
\emph{uniquely} determine $f$.  That is, if $f$ is a function
satisfying~(\ref{f>=10}) and~(\ref{f<10}), then $f(n)$ equals the value you
specified in part~(\ref{simpledef}) for all $n \in \naturals$.

\solution{
\begin{proof}
Assume (for contradiction) that $f$ is a function satisfying~(\ref{f>=10})
and~(\ref{f<10}), but $f(n) \neq f_0(n)$ for some $n \in \naturals$.

We know that $f_0(n) = n-3 = f(n)$ for $n \ge 10000$, by equation~(\ref{n-3})
in the definition of $f_0$ and equation~(\ref{f>=10}) for $f$.  So it must
be that $f(9999 -m) \neq f_0(9999-m)$ for some natural number $m \le
9999$.  Let $k$ be the least such $m$.

We already observed in part~(a) that $k > 3$.  We can show that this implies
$k \neq 4$, which, in term, implies $k > 4$
\begin{align*}
f(9999-4)& = f(9995)\\
         & = f(f(9995+5)) & \text{by~(\ref{f<10})}\\
         & = f(f(10000))\\
         & = f(9997) & \text{by~(\ref{f>=10})}\\
         & = f(9999-2)\\
         & = f_0(9999-2) & \text{since $k>2$}\\
         & = f_0(9997)\\
         & = 9998 & \text{by~(\ref{odd})}\\
         & = f_0(9995) & \text{by~(\ref{odd})}\\
         & = f(9999-4).
\end{align*}

But now if $k\ge 5$ is odd, we have
\begin{align*}
f(9999 - k) & = f(f((9999 - k) +5)) & \text{by~(\ref{f<10})}\\
             & = f(f((9999 - (k -5))))\\
             & = f(f_0((9999 - (k -5)))) & \text{since $0 \le k-5 <k$}\\
             & = f(9998) & \text{by~(\ref{odd})}\\
             & = f(9999-1)\\
             & = f_0(9999-1) & \text{since $k>1$}\\
             & = f_0(9998)\\
             & = 9997 & \text{by~(\ref{even})}\\
             & = f_0(9999-k) & \text{by~(\ref{even}) since $9999-k$ is even},
\end{align*}
contradicting the fact that $f(9999 - k) \neq f_0(9999-k)$.

A similar argument applies if $k\ge 5$ is even.  Hence there is no $k$
such that $f(9999-k) \neq f_0(9999-k)$, which implies $f=f_0$.

\end{proof}}

\end{problemparts}
\end{problem}

\iffalse
GIVEN QUIZ 2 EXPERIENCE IN NOVEMBER 2002, IT'S CLEAR WE SHOULD HAVE
CHOSEN AN ANNUITY PROBLEM HERE.
\fi

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

\begin{problem} \textbf{Closed Form Summations}

Find a simplified closed form for each of the expressions listed below.

\bparts
\problempart $ \sum_{i=x}^{y} 2i+1 $

\solution{
There are two ways of doing this problem.  In the first, we re-form the 
sum so the lower limit is 0 instead of $x$ and apply the arithmetic sum 
formula.  

$$\sum_{i=x}^y 2i+1 = \sum_{i=0}^{y-x} 2(i+x)+1$$
$$= \sum_{i=0}^{y-x} 2i + 2x+1$$
$$= (y-x+1)(2x+1) + 2 \sum_{i=0}^{y-x} i $$
$$= (y-x+1)(2x+1) + 2 \frac{(y-x)(y-x+1)}{2} $$
$$= (y-x+1)(2x+1 + y-x) = (y-x+1)(y+x+1) = ((y+1)-x)((y+1)+x) $$
$$= (y+1)^2 - x^2.$$


In the second, we express this sum as the difference of two summations,
one involving only $y$ and one involving only $x$.  
$$
\sum_{i=x}^{y} 2i+1 = \sum_{i=0}^{y} 2i + 1 - (\sum_{i=0}^{x-1} 2i +
1).
$$
Now, since 

$$\sum_{i=0}^n 2i+1 = n+1 + 2\frac{n(n+1)}{2} = n+1 + n(n+1) = n^2 +
2n+1 = (n+1)^2,$$

we can evaluate this to

$$(y+1)^2 - x^2.$$
}

\problempart
${\displaystyle \sum_{i=0}^{\infty} \sum_{j=1}^n \left(\cfrac{j}{j+2}\right)^i}$

\solution{
First, we reorder the summations to get

$$\sum_{j=1}^n \sum_{i=0}^{\infty} \left(\frac{j}{j+2}\right)^i.$$

We can do this reordering because the value of $j$ never depends on the
value of $i$, we just use every possible pair of values for a nonnegative 
$i$ and a $j$ between 1 and $n$.

Evaluating the inner summation, which is just an infinite geometric
series, we get

$$\sum_{j=1}^n \cfrac{1}{1 - \cfrac{j}{j+2}}$$
$$= \sum_{j=1}^n \cfrac{j+2}{2}$$
$$= n + \frac{1}{2}\sum_{j=1}^n j$$
$$= n + \cfrac{n(n+1)}{4}$$

which simplifies to $\frac{1}{4}n^2 + \frac{5}{4}n$.

}

\ppart ${\displaystyle \prod_{i=1}^n 2 \cdot 4^i}$.

\solution{
We know that $\prod_{i=1}^n 2 \cdot 4^i =(2\cdot4^1) \cdot (2\cdot4^2) \cdot ... \cdot (2\cdot4^n).$
Taking $\log_2$ of both sides of the equation gives us
\begin{eqnarray*}
\log_2(\prod_{i=1}^n 2\cdot4^i)&=&\log_2(2\cdot4^1 \cdot 2\cdot4^2 \cdot ... \cdot 2\cdot4^n)\\
&=&\log_2(2\cdot4^1)+\log_2(2\cdot4^2)+...+\log_2(2\cdot4^n)\\
&=&\sum_{j=1}^n\log_2(2\cdot4^j)\\
&=&\sum_{j=1}^n(\log_2(2) + \log_2(4^j))\\
&=&\sum_{j=1}^n (1 +  2j)\\
&=&n+n(n+1)\\
&=&n^2+2n.
\end{eqnarray*}
Now, exponentiating both sides of the equation gives
$\prod_{i=1}^n 2\cdot4^i=2^{n^2+2n}$
}

\eparts
\end{problem}

\begin{problem}
Let $S_n = \sum_{i=1}^n i^{1 /3}$.  Use the integral method to determine a
constant $c \in \reals$ such that
\[
S_n \sim cn^{\frac{4}{3}}.
\]

\solution{$c = 3/4$.

We use the integral method for bounding $S_n$. 
\[\int_0^n x^{\frac{1}{3}}dx \leq S_n \leq \int_1^{n+1}x^{\frac{1}{3}}dx.\]
That is,
\[\frac{(3/4)n^{4/3}}{n^{4/3}}  \leq \frac{S_n}{n^{4/3}} \leq
\frac{(3/4)((n+1)^{4/3} - 1)}{n^{4/3}}
\]
Taking limits as $n \to \infty$ we find that
\[
3/4 \leq {\displaystyle \lim_{n \to \infty}\frac{S_n}{n^{4/3} }}
\leq 3/4\]

Therefore, ${\displaystyle \lim_{n\to\infty}\frac{S_n}{n^{4/3}}} = 3/4.$
}

\end{problem}


\begin{problem}

Use the integral method to find upper and lower bounds for the following
summation that differ by at most 0.1.
\[
\sum_{i=1}^{\infty} \frac{1}{i^2}
\]
\hint Try adding the first few terms explicitly and then use integrals to
bound the sum of the remaining terms.

\solution{
We can bound the summation above as follows:

\begin{eqnarray*}
\sum_{i=1}^{\infty} \frac{1}{i^2}
    & \leq &    \frac{1}{1} + \frac{1}{4} + \frac{1}{9} +
            \int_3^{\infty} \frac{1}{x^2} \ dx \\
    & = &       \frac{1}{1} + \frac{1}{4} + \frac{1}{9} +
            \left( - \frac{1}{x} \right)_3^{\infty} \\
    & = &       \frac{1}{1} + \frac{1}{4} + \frac{1}{9} +
            \frac{1}{3} \\
    & = &        1.694\ldots
\end{eqnarray*}

We can lower bound the summation similarly:

\begin{eqnarray*}
\sum_{i=1}^{\infty} \frac{1}{i^2}
    & \geq &    \frac{1}{1} + \frac{1}{4} + \frac{1}{9} +
            \int_3^{\infty} \frac{1}{(x+1)^2} \ dx \\
    & & =       \frac{1}{1} + \frac{1}{4} + \frac{1}{9} +
            \left( - \frac{1}{x+1} \right)_3^{\infty} \\
    & & =       \frac{1}{1} + \frac{1}{4} + \frac{1}{9} +
            \frac{1}{4} \\
    & & =       1.611\ldots
\end{eqnarray*}
}

(The actual value of the summation turns out to be $\pi^2 / 6 =
1.644\ldots$.)  

\end{problem}


\begin{problem} \textbf{Growing Choices}

The expression $\binom{n}{k}$ is read ``$n$
choose $k$'' and represents the quantity
\[\frac{n!}{k! \ (n-k)!}.\]
This expression comes up frequently in probability and combinatorics
and will be used extensively later in this course.  Suppose that $n$
is even.  Prove that

\begin{eqnarray*}
\binom{n}{n/2}
	& & =	\Theta(2^n / \sqrt{n}).
\end{eqnarray*}

Use the following form of Stirling's formula:

\begin{eqnarray*}
n!	& \sim &	\sqrt{2 \pi n} \left(\frac{n}{e}\right)^n
\end{eqnarray*}

\solution{
Though substituting in Stirling's formula initially gives a
complicated expression, most of the square roots and the exponentials
cancel.

\begin{eqnarray*}
\binom{n}{\alpha n}
	& = &	\frac{n!}{(\alpha n)! \ ((1-\alpha) n)!} \\
	& \sim &	\frac{\sqrt{2 \pi n} \left(\frac{n}{e}\right)^n}
	{\sqrt{2 \pi \alpha n} \left(\frac{\alpha n}{e}\right)^{\alpha n}
	\cdot
	\sqrt{2 \pi (1-\alpha) n} \left(\frac{(1-\alpha) n}{e}\right)^{(1-\alpha) n}} \\
	& = &	\frac{1}{\sqrt{2 \pi n \alpha (1 - \alpha)}} \cdot
		\frac{1}{\alpha^{\alpha n} \cdot (1-\alpha)^{(1-\alpha)n}}
\end{eqnarray*}

Letting $\alpha = 1/2$,
\begin{eqnarray*}
\binom{n}{n/2}
	& \sim & 	\frac{1}{\sqrt{2 \pi n (1/2) (1 - 1/2)}} \cdot
		\frac{1}{(1/2)^{n/2} \cdot (1 - 1/2)^{(1 - 1/2)n}} \\
	& = & 	\frac{1}{\sqrt{\pi n/2}} \cdot
		\frac{1}{(1/2)^{n/2} \cdot (1/2)^{n/2}} \\
	& = &	\frac{1}{\sqrt{\pi/2}} \cdot \frac{2^n}{\sqrt{n}} \\
	& = &	\Theta\left(\frac{2^n}{\sqrt{n}}\right).
\end{eqnarray*}
}
\end{problem}


\iffalse

\begin{problem} \textbf{Ordering Orders}

For each pair of functions $(f(n), g(n))$ in the table below, indicate
whether the statement at the top of the column is true (e.g., whether
$f(n) = O(g(n))$).  Assume $k\geq 1$, $\epsilon > 0$, and $c > 1$ are
constants. Your answer should be in the form of a table with ``yes'' or
``no'' in each box.
\begin{equation*}
\begin{array}{|cc|*{3}{c|}}
\hline
f(n) & g(n) & f(n) = O(g(n)) & g(n) = O(f(n)) & f(n) = \Theta(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{equation*}
\begin{array}{|cc|*{3}{c|}}
\hline
f(n) & g(n) & f(n) = O(g(n)) & g(n) = O(f(n)) & f(n) =
\Theta(g(n)) \\\hline\hline
\log^k n & n^\epsilon & \y & \n & \n \\\hline
n^k & c^n & \y & \n & \n \\\hline
\sqrt{n} & n^{\sin n\pi/2} & \n & \n & \n\\\hline
2^n & 2^{n/2} & \n & \y & \n \\\hline
\log(n!) & \log(n^n) & \y & \y & \y \\\hline
\end{array}
\end{equation*}

Following are some hints on deriving the table above:\\ \iffalse (a) See
notes on $O$-notation. (to appear)\\ \fi

Row:

(2) Polynomial growth versus exponential growth. (See Theorem 7.6, Notes
7.)

(3) $n^{\sin n\pi/2}=1$ for even values of $n$.  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$.

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

(5) See Rosen \S 1.8 Ex. 61,62 
}

\end{problem}


\begin{problem} \textbf{Mysterious Convergence}
% problem 3, problem set 6, fall 1996
% similar to CLR 3.2-1

Show that $\sum_{k=1}^{\infty}{1/k^{3/2}}$ is bounded above by a constant.

\solution{
We use the integral method for bounding the infinite sum. Since
$f(k)=\frac{1}{k^{3/2}}$ is monotonically decreasing for $k>1$, we
have:
\begin{eqnarray*}
\sum_{k=1}^\infty{1/{k^{3/2}}} &=& 1 + \sum_{k=2}^\infty{1/{k^{3/2}}} \\
&\leq& 1+ \int_1^\infty{\frac{1}{x^{3/2}}}dx\\
&=& 1 + \left [{\frac{-2}{\sqrt{x}}}\right ]_1^\infty\\
&=& 1 + (0 + 2)\\
&=& 3
\end{eqnarray*}
Hence, $\sum_{k=1}^\infty{1/{k^{3/2}}} \leq 3$.
}

\end{problem}

\begin{problem} \textbf{Bounding Infinity}
% not multiple choice (but could be)

Using the Integral Method, give an upper bound for 
\[\sum_{i=1}^n \frac{3}{i^{10}} \] 
 
\solution{
Since $f(k)=\frac{3}{i^{10}}$ is monotonically decreasing for $x>1$, we have:
    \begin{eqnarray*}
      \sum_{i=1}^n{\frac{3}{i^{10}}} &=& 3 + \sum_{i=2}^n{\frac{3}{i^{10}}} \\
      &\leq& 3+ \int_1^n{\frac{3}{x^{10}}}dx\\
      &=& 3+ 3\int_1^n{\frac{1}{x^{10}}}dx\\
      &=& 3 + 3\left [{\frac{-1}{9x^{9}}}\right ]_1^n\\
      &=& 3 + \left [{\frac{-1}{3x^{9}}}\right ]_1^n\\
      &=& 3 - \frac{1}{3n^{9}} + \frac{1}{3}\\
      &=& \frac{10}{3} - \frac{1}{3n^{9}}
    \end{eqnarray*}
    Hence, $\sum_{i=1}^n \frac{3}{x^{10}} \leq \frac{10}{3} - \frac{1}{3n^{9}}$.

}

\end{problem}
\fi

 
\begin{problem} \textbf{Asymptotic Notation}

Determine which of the eight choices below best describes each function's
asymptotic behavior.  Briefly indicate your reasoning; you may appeal to
any of the results in the Notes or Rosen.
\[\begin{array}{ll}
\theta (n) &\theta (n!)\\
\theta (n\log n) & \theta (n^2)\\
\theta (1)& \theta (2^n)\\
2^{f(n)}\text{ where }f=\theta(n) & \text{None of the above}
\end{array}\]

\bparts

\problempart  $g(n) \eqdef  n + \ln n + (\ln n)^2$.

\solution{$\theta(n)$.

We know that $(\ln n)^2 = o(n)$ and $\ln n = o((\ln n)^2)$, so for
sufficiently large $n$
\[
n > (\ln n)^2 > \ln n.
\]
Thus, for sufficiently large $n$,
\[
n + \ln n + (\ln n)^2 < n + n + n = 3n.
\]

Furthermore, as long as $\ln n$ is positive, 
\[
n + \ln n + (\ln n)^2 > n.
\]

Thus, for all sufficiently large $n$,  $n < g(n) < 3n$, so $g(n) = 
\theta(n)$.  
}


\problempart $h(n) \eqdef (n^2 + 2n - 3)/(n^2 - 1)$

\solution{$\theta(1)$.

Dividing the top and bottom by $n-1$ yields

$h(n) = \frac{n+3}{n+1}$.  

Now, since the top is greater than the bottom, $h(n) > 1$ for all $n > -1$.
Furthermore, solving the equation $\frac{n+3}{n+1} < 2$ yields the solution
$n > 1$.  So for all $n > 1$, $h(n) < 2$.  

Thus, for all $n > 1$, we have $1 < h(n) < 2$ so $h(n) = \theta(1)$.
}


\problempart $j(n) \eqdef \sum_{i = 0}^n 2^{2i+1}$

\solution{$2^{\theta(n)}$.

Putting the summation in closed form yields $j(n) = 2(4^n)/3$.

Now certainly, $\log_2 j(n) = \log_2(2/3) + n\log_2(4) = \theta(n)$.
Thus, $j(n) = 2^{\theta(n)}$.  However, as shown in
\href{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln7.pdf}
{Week 7 Notes}, \S7.4, $\neg [4^n = O(2^n)]$, so $\neg [j(n) =
\theta(2^n)]$.  Therefore, $2^{\theta(n)}$ best describes the asymptotic
behavior of $j(n)$.
}


\problempart $k(n) \eqdef (2 + \sin (n))2^{n + \sin(n)}$.

\solution{$\theta(2^n)$.

We know that $\sin n \geq -1$ so $k(n) \geq (2-1)2^{n-1} = \frac122^n$.

We also know that $\sin n \leq 1$ so $k(n) \leq (2+1)2^{n+1} = 6\cdot2^n$.

Thus, $\frac12 2^n \leq k(n) \leq 6\cdot2^n$, so $k(n) = \theta(2^n)$.
}


\problempart $f(n) \eqdef \ln ((n^2)!)$.

\solution{None of the above.

By Stirling's approximation, we know that $f(n) = \theta(n^2 \ln n^2) =
\theta (n^2 \ln n)$.  So $f$ grows faster than $\theta(1), \theta(n),
\theta(n^2)$ and $\theta(n \log n)$, and slower than $\theta(n!),
\theta(2^n)$ and $2^{\theta(n)}$, so ``none of these'' is the correct
answer. 

}
\eparts

\end{problem}

\end{document}


\iffalse

\begin{problem}


Find closed-form expressions for the following sums.

\begin{problemparts}

\iffalse

%\problempart
\[
\sum_{i=0}^n \frac{9^n - 7^n}{11^n}
\]

\solution{
Split the expression into two geometric series and then
apply the formula for the sum of a geometric series.

\begin{eqnarray*}
\sum_{i=0}^n \frac{9^i - 7^i}{11^i}
    & = &   \sum_{i=0}^n \left(\frac{9}{11}\right)^i -
        \sum_{i=0}^n \left(\frac{7}{11}\right)^i \\
    & = &   \frac{1 - \left(\frac{9}{11}\right)^{n+1}}{1 - \frac{9}{11}}
          - \frac{1 - \left(\frac{7}{11}\right)^{n+1}}{1 - \frac{7}{11}} \\
    & = &   - \frac{11}{2} \cdot \left(\frac{9}{11}\right)^{n+1}
        + \frac{11}{4} \cdot \left(\frac{7}{11}\right)^{n+1}
        + \frac{11}{4}
\end{eqnarray*}

}
\fi

\problempart
\[
\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} \sum_{k=0}^{\infty} 2^{-(i +2j +3k)}
\]

\solution{
 Apply the formula for the sum of a geometric series three
times.

\begin{eqnarray*}
\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} \sum_{k=0}^{\infty} 2^{-(i +2j +3k)}
    & = &   \sum_{i=0}^{\infty} 2^{-i} \cdot
        \left(\sum_{j=0}^{\infty} 2^{-2j} \cdot
        \left(\sum_{k=0}^{\infty} 2^{-3k} \right) \right) \\
    & = &   \sum_{i=0}^{\infty} 2^{-i} \cdot
        \left(\sum_{j=0}^{\infty} 2^{-2j} \cdot
        \frac{8}{7} \right) \\
    & = &   \sum_{i=0}^{\infty} 2^{-i} \cdot
        \frac{4}{3} \cdot \frac{8}{7} \\
    & = &   \frac{2}{1} \cdot \frac{4}{3} \cdot \frac{8}{7} \\
    & = &   \frac{64}{21}
\end{eqnarray*}
}

%\iffalse

\problempart
\[
\sum_{i=n+1}^{2n} i^2
\]

\solution{

This expression is the difference of two sums of squares, which can be
reduced to a closed form by a standard formula.

\begin{eqnarray*}
\sum_{i=n+1}^{2n} i^2
    & = &   \sum_{i=1}^{2n} i^2 - \sum_{i=1}^{n} i^2 \\
    & = &   \frac{(2n)(2n+\frac{1}{2})(2n+1)}{3} -
        \frac{n(n+\frac{1}{2})(n+1)}{3} \\
    & = &   \frac{7}{3} n^3 + \frac{3}{2} n^2 + \frac{1}{6} n \\
    & = &   \frac{n (2n + 1) (7n + 1)}{6}
\end{eqnarray*}
}

\problempart
\[
\prod_{i=1}^{n} 3^{4i + 5}
\]

\solution{

This product can be reduced to an easy sum by taking a
logarithm.

\begin{eqnarray*}
\prod_{i=1}^{n} 3^{4i + 5}
    & = &   3^{\log_3\left( \prod_{i=1}^{n} 3^{4i + 5} \right)} \\
    & = &   3^{\sum_{i=1}^n 4i+5} \\
    & = &   3^{2n(n+1) + 5n}
\end{eqnarray*}
}
%\fi

\problempart

\[
\sum_{j=1}^n \sum_{i=0}^{\infty} j^{2/3} \cdot \left(1 - \frac{1}{2 j^{1/3}}\right)^i
\]

\solution{

This fearsome-looking sum is a paper tiger; we just apply
the formula for the sum of a geometric series followed by the formula
for the sum of an arithmetic series.

\begin{eqnarray*}
\sum_{j=1}^n \sum_{i=0}^{\infty} j^{2/3} \cdot \left(1 - \frac{1}{2 j^{1/3}}\right)^i
    & = &   \sum_{j=1}^n j^{2/3} \cdot \frac{1}{1 - \left(1 - \frac{1}{2 j^{1/3}}\right)} \\
    & = &   \sum_{j=1}^n 2j \\
    & = &   n (n+1)
\end{eqnarray*}
}
\iffalse

\problempart

\[
\prod_{i=2}^{n} \left(1 - \frac{1}{i^2}\right)
\]

\solution{ 

We give two solutions.  First, evaluating a few terms
suggests that the product is equal to

\[
\frac{n+1}{2n}.
\]

We could verify this by induction.  The calculation needed for the
inductive step is shown below.

\begin{eqnarray*}
\prod_{i=2}^{n+1} \left(1 - \frac{1}{i^2}\right)
    & = &   \left(1 - \frac{1}{(n+1)^2}\right) \cdot
        \prod_{i=2}^{n} \left(1 - \frac{1}{i^2}\right) \\
    & = &   \left(1 - \frac{1}{(n+1)^2}\right) \cdot
        \frac{n+1}{2n} \\
    & = &   \frac{(n+1)+1}{2(n+1)}
\end{eqnarray*}

As an alternative approach, we might observe that this is a
``telescoping product''.

\begin{eqnarray*}
\prod_{i=2}^{n} \left(1 - \frac{1}{i^2}\right)
    & = & \prod_{i=2}^{n} \frac{(i-1)(i+1)}{i^2} \\
    & = & \frac{1 \cdot 3}{2 \cdot 2}
        \cdot \frac{2 \cdot 4}{3 \cdot 3}
        \cdot \frac{3 \cdot 5}{4 \cdot 4} \cdots
        \frac{(n-1) \cdot (n+1)}{n \cdot n} \\
    & = &   \frac{1}{2} \cdot {n+1}{n}
\end{eqnarray*}
}
\fi

\end{problemparts}

\end{problem}

\fi

\iffalse

\begin{problem}
\begin{problemparts}

\problempart 
What is the product of the first $n$ odd powers of two:
$\prod\limits_{k=1}^n2^{2k-1}$?   

\solution{ 
\[
\Pi_{k=1}^n2^{2k-1} = 2^{\sum_{k=1}^n{2k-1}}
= 2^{2\sum_{k=1}^n k-\sum_{k=1}^n 1}
= 2^{n(n+1) - n}
= 2^{n^2}
\]
}
%\vspace*{2in}
\problempart What is $\sum\limits_{k=a}^b k$?   

\solution{
\[
\sum_{k=a}^b k = 
\sum_{k=1}^b k - \sum_{k=1}^{a-1} k = 
\frac{b(b+1)}{2} - \frac{a(a-1)}{2}
\]

Also, some students computed the same answer directly
in the form
\[
\frac{(a+b)(b-a+1)}{2}
\]
by noticing that the first and last terms sum
to $(a + b)$, the second and next to last terms also
sum to $(a + b)$, etc. This means that we are adding
the term $(a + b)$ a number of times equal to
$\frac{(b - a + 1)}{2}$ sinc there are $(b -a + 1)$ terms
and we take two for each $(a + b)$.

The most common mistake on this part was to sum
up to $a$ instead of $a-1$ using the first approach.
}
%\vspace*{2in}

\problempart
Find upper and lower bounds for 
$$
\sum_{k=1}^n\frac{1}{\sqrt{k}}
$$
which differ by at most 1.    

\solution{
\begin{eqnarray*}
\int_0^n \frac{1}{\sqrt{x+1}} \ dx \leq & \sum_{k=1}^n \frac{1}{\sqrt{k}} & \leq \int_0^n \frac{1}{\sqrt{x}}\ dx \\
\int_0^n \frac{1}{\sqrt{x+1}} \ dx \leq & \sum_{k=1}^n \frac{1}{\sqrt{k}} & \leq 1 + \int_1^n \frac{1}{\sqrt{x}}\ dx \\
2\sqrt{n+1} - 2 \leq & \sum_{k=1}^n \frac{1}{\sqrt{k}} & \leq 1 + 2\sqrt{n} - 2\\
2\sqrt{n+1} - 2 \leq & \sum_{k=1}^n \frac{1}{\sqrt{k}} & \leq 2\sqrt{n} - 1
\end{eqnarray*}

The most common mistake on this part of the problem was
having the wrong limits of integration (going from $1$ to $n$
instead of from $0$ to $n$). The more severe (and less common)
mistake was to switch the two functions for the upper and lower
bound.
}
\end{problemparts}

\end{problem}

\begin{problem}
We begin with two large glasses.  The first glass contains a pint of
water, and the second contains a pint of wine.  We pour 1/3 of a pint
from the first glass into the second, stir up the wine/water mixture in
the second glass, and then pour 1/3 of a pint of the mix back into the
first glass and repeat this pouring back-and-forth process a total of
$n$ times.
\begin{problemparts}
\problempart
Describe a closed form formula for the amount of wine in the first glass
after $n$ back-and-forth pourings.

\solution{The state of the system of glasses/wine/water at the beginning
of a round of pouring and pouring back is determined by the total amount
of wine in the first glass.  Suppose at the beginning of some round, the
first glass contains $w$ pints of wine, $0\leq w \leq 1$ and $1-w$ pints
of water.  The second glass contains the rest of the wine and water.

Pouring 1/3 pint from first glass to second leaves 2/3 pints of liquid and
$(2/3)w$ wine in the first glass, and 4/3 pints of liquid and 
$1 - (2/3)w$ wine 
in the second glass.  Pouring 1/3 pint back from second into first
transfers a proportion of (1/3)/(4/3) of the wine in the second glass into
the first.  So the round completes with both glasses containing a pint of
liquid, and the first glass containing
\[
(2/3)w + (1/4)(1- (2/3)w) = 1/4 + w/2
\]
pints of wine.  After one more round, the first glass contains
\[1/4 + (1/4 + w/2)/2 = 1/4 + 1/8 + w/2^2\]
pints of wine, and after $n$ more rounds
\[
\begin{array}{lll}
w/2^n + \Sigma_{i=1}^n (1/2)^{i+1} &=  w/2^n + (1/2)\Sigma_{i=1}^n
(1/2)^{i}\\
& = w/2^n + (1/2)(-1 + \Sigma_{i=0}^n (1/2)^{i})\\
& = w/2^n + (1/2)(-1 + (1 - (1/2)^{n+1})/(1 - 1/2))\\
& = w/2^n - 1/2 + 1 - (1/2)^{n+1}\\
& = w/2^n + 1/2 - (1/2)^{n+1}.
\end{array}
\]
Since $w=0$ initially, the pints of wine in the first glass
after $n$ rounds is
\[
1/2 - (1/2)^{n+1}.
\]
}

\problempart
What is the limit of the amount of wine in each glass as $n$ approaches infinity?
\end{problemparts}

\solution{
The limiting amount of wine in the first glass approaches 1/2 from below
as $n$ approaches infinity.  In fact, it approaches 1/2 no matter how the
wine was initially distributed.  This of course is what you would expect:
after a thorough mixing the glasses should contain essentially the same
amount of wine.
}
\end{problem}
\fi
