\documentclass[12pt,twoside]{article}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\graphicspath{{../problemRepository/figs/}}
\usepackage{amsmath}
\usepackage{psfig}  
\input{../handouts/macros-course}
\newcommand{\cross}{\times}
\newcommand{\eqdef}{\mathbin{::=}}



%\def\cent{{\not\!\mathrm{c}}}
\renewcommand{\implies}{\longrightarrow}
\renewcommand{\labelenumi}{\arabic{enumi})}  
\setlength{\itemsep}{0cm}

%\newcommand{\solution}[1]{}
%\newcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}
\askaboutsolutions

\begin{document}
\handout{tut6}{Mini-Quiz 6}{March 16, 2001}
\begin{enumerate}
\item Your name:
\item Find the least integer n such that $f(x)$ is $O(x^{n})$ for each of the following functions.
\bparts
\ppart $f(x) = {2x^3 + (log   x) x^2}$
\ppart $f(x) = 3x^3 + (log   4)^4 $
\ppart $f(x) = \frac{x^4 + x^2 + 1}{x^3+1}$
\ppart $f(x) = \frac{x^4 + 5log   x}{x^4 + 1}$
\eparts
\end{enumerate}
\newpage
\thispagestyle{empty}
\mbox{}
\setcounter{page}{0}
\newpage
\handout{tut6}{Tutorial 6 Problems}{March 16, 2001}
\begin{problems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\problem Is a Harvard degree really worth more than an MIT degree?!  Let
us say that a person with a Harvard degree starts with \$40,000 and gets a
\$20,000 raise every year after graduation, whereas a person with an MIT
degree starts with \$30,000, but gets a 20\% raise every year.  Assume
inflation is a fixed $8\%$ every year.  That is, \$1.08 a year from now is
worth \$1.00 today.  (You'll need a calculator to get final answers; if
one is not available, it's ok to express the answer as a closed form
numerical expression.)

\bparts


\ppart How much is a Harvard degree worth today if the holder will work
for $n$ years following graduation? 

\ppart How much is an MIT degree worth in this case?

\ppart If you plan to retire after twenty years, which degree would
be worth more?

\solution{
One dollar after year $i$ is worth $r^i$ in today's currency, where
\[
r= \frac{1}{1.08} = 0.925\, 925\, 925 \dots
\]
So 
\begin{eqnarray*}
\mbox{Hvd}_n & = & \sum_{i=0}^{n} (40000+ 20000i)r^i\\
        & = & 40000\sum_{i=0}^{n} r^i + 20000\sum_{i=0}^{n} i r^i,\\
\mbox{MIT}_n & = & 30000\sum_{i=0}^{n} {1.2}^i r^i\\
        & = & 30000\sum_{i=0}^{n} (1.2r)^i
\end{eqnarray*}

But
\[
\sum_{i=0}^{n} ir^i = \frac{{r - (n+1) r^{n+1} + n r^{n+2}}}{(1-r)^2},
\]
so 
\begin{eqnarray*}
\mbox{Hvd}_n & = & 40000 \frac{(1- r^{n+1})}{1- r}  + 
                   20000 \frac{(r - (n+1) r^{n+1} + n r^{n+2})}{(1-r)^2}\\
  & = &  \frac{20000(2(1- r^{n+1} -r +r^{n+2}) + r - (n+1) r^{n+1} + n r^{n+2})}{(1-r)^2}\\
  & = &  \frac{{20000(2 - r - (n+3)r^{n+1} + (n + 2)r^{n+2})}}{(1-r)^2}\\
\mbox{MIT}_n & = &  \frac{{30000(1 - (1.2r)^{n+1})}}{1 - 1.2r}
\end{eqnarray*}
and for $n=20$,
\begin{eqnarray*}
\mbox{Hvd}_{20} & = &  \frac{{20000(2 - r - 23r^{21} + 22r^{22})}}{(1-r)^2} = 2,010,885\\
\mbox{MIT}_{20} & = &  \frac{{30000(1 - (1.2r)^{21})}}{1 - 1.2r} = 2,197,579.
\end{eqnarray*}

so the MIT degree is more valuable! (But we knew that already.)}

\eparts

\problem How many slices of pizza can a person obtain by making n straight cuts with a pizza knife?  First, find a recurrence and then a closed form for the recurrence you found. 
\smallskip
\solution{
\textbf{Solution:}
The best way to start this problem is to draw it out for a few initial cuts and see if a pattern can be found.  
For the nth line (for n $>$ 0), it can increase the number of regions by k if it
splits k old regions, which it can do by hitting the lines already there 
in k-1 places.  Since two lines can only intersect in one point, the new line
can only intersect the n-1 old lines at n-1 different points.  Therefore, 
our upper bound for how many regions we can have is:
\begin{eqnarray*}
L_n & \leq & L_{n-1} + n
\end{eqnarray*}

We can make this an equality by placing our nth line so that it is NOT parallel to any existing line.  

Now, we'll find the closed for by plug and chug.  Notice that the sequence starts off as 1, 2, 4, 7, 11, 16, $\cdot$ $\cdot$ $\cdot$


$\begin{array}{lll}
L_n & =&  L_{n-1} + n\\
& = &L_{n-2} + (n - 1) + n\\
& =& L_{n-3} + (n-2) + (n-1) + n\\
&  \cdot& \\
&  \cdot& \\
&  \cdot& \\
& =& L_0 + 1 + 2 + \cdot \cdot \cdot + (n - 1) + n \\
\end{array}$


Recall that the sum:
\[\begin{array}{lll}
1 + 2 + \cdot \cdot \cdot + (n - 1) + n &=& \frac{n(n+1)}{2}  \quad \text{(for $n \geq 0$)}
\end{array}\]
Thus, our final closed form is:\[
\begin{array}{lll}
L_n &=& \frac{n(n+1)}{2} + 1
\end{array}\]
}

\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.
A linear recurrence can be written as:
\[T(n) = \frac{1}{2} T(n-1) + \frac{1}{4}\] 

Given the recurrence, we find the closed form formula to be:
\[
\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


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

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

\problem
We shall define the falling factorial powers as follows:
\begin{eqnarray*}
x^{\underline{m}} = x(x-1) \cdot \cdot \cdot (x - m + 1)  \quad \text{(for integer $m \geq 0$)}
\end{eqnarray*}

Prove that

$$\sum_{0 \le k < n} (k^{\underline{m}}) = \frac{n^{\underline{m+1}}}{m+1} \quad \text{(for integers $m,n \ge 0$)}$$
%=======
%$\sum_{0 \le k < n} (k^{\underline{m}}) = \frac{n^{\underline{m+1}}}{m+1} \quad$ \text{(for integers $m,n \ge 0$)}


\solution{
 \textbf{Solution:}
The crucial step is to rewrite $x^{\underline{m}}$ as $\frac{(x+1)^{\underline{m+1}} - x^{\underline{m+1}}}{m+1}$.

To see why this is:

$\begin{array}{lll}
(x+1)^{\underline{m+1}} - x^{\underline{m+1}} & =& (x+1)(x)(x-1) \cdot \cdot \cdot (x+1-(m+1)+1) - (x)(x-1)(x-2) \cdot \cdot \cdot (x-(m+1)+1) \\
& =& (x+1)(x)(x-1) \cdot \cdot \cdot (x-m+1) - (x)(x-1)(x-2) \cdot \cdot \cdot (x-m) \\
& =& (x+1-(x-m))(x)(x-1)(x-2)....(x-m+1) \\
& =& (x+1-(x-m)) x^{\underline{m}} \\
& =& (m+1) x^{\underline{m}} \\
\end{array}$

\begin{eqnarray*}
x^{\underline{m}}  &=& \frac{(x+1)^{\underline{m+1}} - x^{\underline{m+1}}}{m+1}\\
\end{eqnarray*}

Now that we have established this relationship, we can use it to find the 
summation.
$\begin{array}{lll}
\sum_{0 \le k < n}(k^{\underline{m}}) & =& \sum_{0 \le k < n} (\frac{(k+1)^{\underline{m+1}} - k^{\underline{m+1}}}{m+1})\\
& =&  \frac{1}{m+1} (1^{\underline{m+1}} - 0^{\underline{m+1}}) + (2^{\underline{m+1}} - 1^{\underline{m+1}}) + (3^{\underline{m+1}} - 2^{\underline{m+1}}) + \cdot \cdot \cdot\\
& +&  ((n-1)^{\underline{m+1}} - (n-2)^{\underline{m+1}}) + (n^{\underline{m+1}} - (n-1)^{\underline{m+1}}) \\
& = &  \frac{1}{m+1} (n^{\underline{m+1}} - 0^{\underline{m+1}}) \\
& = &\frac{n^{\underline{m+1}}}{m+1} \\
\end{array}$
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problems}
\end{document}