%\input{params}
\documentclass[11pt,twoside]{article}
    
\usepackage{graphics}
\newcommand{\nand}{|}

\input{macros-course}

\def\cent{{\not\!\mathrm{c}}}

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

\printlayout
\askaboutsolutions

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

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\tutref}{tut7}
\newcommand{\tutnum}{7}
\newcommand{\tutdate}{October 20, 2000}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\handout{\tutref}{Tutorial \tutnum~Problems}{\tutdate}

\begin{problems}


\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}
\]
Prove that 
\[
\sum_{k \ge 2} (\zeta(k)-1) = 1
\]

%\textbf{Hint:} Recall from problem set~5, problem 2, that
%$\sum_{k=2}^n {\frac{1}{k(k-1)}} = 1 - \frac{1}{n}$.

\solution{

 \textbf{Solution:}

 First, we prove that $\sum_{k=2}^n {\frac{1}{k(k-1)}} = 1 - \frac{1}{n}$
 
 \smallskip 
 By using partial fractions, we find that $\frac{1}{k(k-1)} = \frac{1}{k-1} - \frac{1}{k}$.\\
So we have:
 
\begin{eqnarray*}
\sum_{k=2}^n {\frac{1}{k(k-1)}} & = & 
\sum_{k=2}^n \left(\frac{1}{k-1} - \frac{1}{k} \right)  \\
 & = & \sum_{k=2}^n \frac{1}{k-1} - \sum_{k=2}^n\frac{1}{k}  \\
 & = & \frac{1}{1} + \frac{1}{2} + \ldots + \frac{1}{n-2} + \frac{1}{n-1} \;\; -\\
 &   & \left[ \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n-1} + \frac{1}{n} \right]
\end{eqnarray*}

So all that does not cancel out is $1 - \frac{1}{n}$.

\bigskip  
We now prove that $\sum_{k \ge 2} (\zeta(k)-1) = 1$ 

  \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] \\
    & = & \sum_{k \ge 2} \sum_{j \ge 2} \frac{1}{j^k} \\
    & = & \sum_{j \ge 2} \sum_{k \ge 2} \frac{1}{j^k} \\
    & = & \sum_{j \ge 2} \frac{1}{j^2} \sum_{k \geq 0} \frac{1}{j^k} \\
    & = & \sum_{j \ge 2} \frac{1}{j^2} \cdot \frac{1}{1 - 1/j} \\
    & = & \sum_{j \ge 2} \frac{1}{j (j - 1)} \\
    & = & \lim_{n \rightarrow \infty} \sum_{j = 2}^{n} \frac{1}{j (j - 1)} \\
    & = & \lim_{n \rightarrow \infty} (1 - \frac{1}{n}) \\
    & = & 1
  \end{eqnarray*}
  }

\medskip

\problem 
% problem 8, problem set 9, Spring 1997
By manipulating summations, without recourse
to induction, prove that
\[
\sum_{k=1}^n H_k = (n+1)H_n-n
\]

\solution{
 \textbf{Solution:}

  \begin{eqnarray*}
  \sum_{k=1}^n H_k & = & \sum_{k=1}^{n} \sum_{j=1}^k {1\over j} \\
  &=& \sum_{1\leq j\leq k\leq n} {1\over j} \\
  &=& \sum_{j=1}^{n} \sum_{k=j}^n {1\over j} \\
  &=& \sum_{k=1}^n{n-j+1\over j} \\
  &=& \sum_{k=1}^n\left({n+1\over j} - 1\right) \\
  &=& (n+1)\sum_{j=1}^{n}{1\over j}-n \\
  &=& (n+1)H_n - n
 \end{eqnarray*}
}

\medskip

\problem \textbf{Asymptotic notation}
% problem 4, problem set 5, fall 1997

Given that $f(x) = O(g(x))$, prove or disprove the following:

\bparts
\ppart
$2^{f(x)} = O(2^{g(x)})$

\solution{%
  \textbf{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. %
  }

\ppart 
$f(x)^2 = O(g(x)^2)$

\solution{%
\textbf{Solution:}
  The above does hold.  Since $f(x) = O(g(x))$, $\exists x_0,c$ such
  that $\forall x \geq x_0, |f(x)| \leq cg(x)$.  So, $\forall 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 $\forall x \geq x_0', f(x)^2 \leq
  c'g(x)^2$.  So $f(x)^2 =
  O(g(x)^2)$. %
  }

\eparts

\medskip

\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.  We now repeat this pouring back-and-forth process a total of
$n$ times.
\bparts

\ppart
Describe a closed form formula for the amount of wine in the first glass
after $n$ back-and-forth pourings.

\ppart
What is the limit of the amount of wine in each glass as $n$ approaches infinity?
\eparts

\solution{
\textbf{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.  Initially, the first glass
contains one pint of water and no wine.  Suppose the first glass contains
$w$ pints of wine, $0\leq w \leq 1$.  Since we're at the beginning of a
round, it contains one pint of liquid, and therefore contains $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 pint of liquid and
$(2/3)w$ wine in the first glass, and 4/3 pints 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 the second round, the first glass contains
\[1/4 + (1/4 + w/2)/2 = 1/4 + 1/8 + w/2^2\]
pints of wine, and after the $n$th round
\[
\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}
\]
So when $w=0$ initially, the pints of wine in the first glass is
\[1/2 - (1/2)^{n+1}.\]
You would expect after a thorough mixing that the glasses would contain
the same amount of wine, viz. 1/2 pint.  Indeed, 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.
}

\medskip

%\newpage
\problem
\bparts
\ppart Give an example of functions $f,g:\naturals\to\naturals$ such that
neither $f = O(g)$ nor $g = O(f)$.  Prove it.

\solution{
\textbf{Solution:} $f(n) = 1 + n(n \bmod 2), g(n) =1 + n ((1 + n) \bmod 2)$.
So $f(n)$ is $n$ times the size of $g(n)$ on odd $n$, vice-versa on even
$n$.
}

\ppart 
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{
\textbf{Solution:} False, let $f_i$ be a constant function with $f(n) =
b(i)$ for all $n$, where $b(i)$ is nonnegative and not $O(2^i)$, for
example, $b(i) = i2^i$.  So $f_i = O(1)$ for each $i$.  Now
\[\sum_{i=1}^n f_i(n) \geq f_n(n) = b(n) \neq O(2^n).\]
}

\eparts


\end{problems}

\end{document}







