\documentclass[11pt, twoside]{article}
\usepackage{epsf}

\input{macros-course}

\newcommand{\nand}{|}
\renewcommand{\implies}{\longrightarrow}

\askaboutsolutions

\begin{document}
\pset{5}{October 17, 2000}{2:35pm in lecture, Tuesday, October 24, 2000}

\textbf{Be sure to indicate your TA's name clearly on the solutions
your turn in}.

-----------------------------------------------------------------------------\\

\textbf{Self-study}
Read: Rosen Section 1.7, 1.8
Self-study problems (not to be handed in): Section 1.7: 5, 8, 9~~~Section 1.8: 7, 13, 14, 21
%[[[Miniquiz for tut5: 11]]]

-----------------------------------------------------------------------------\\

\textbf{Reading:}
Lecture notes;  Rosen 1.7, 1.8 (skim)

\paragraph{Policy on collaboration}
If you collaborated with someone on the problem sets, you should mention their names on top of the problem set. If you did not collaborate with anyone, you should explicitly say so. As a reminder, the write-up of your solutions should be entirely your own.
 
\medskip
\begin{problems}


\problem {\bf (16 points)} 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{ 
 \textbf{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{
\textbf{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 \\
	& = &	j (j+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}

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

\problem {\bf (10 points)} 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{
\textbf{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}{\alpha n}
	& \sim & 	\frac{1}{\sqrt{2 \pi n \alpha (1 - \alpha)}} \cdot
		\frac{1}{\alpha^{\alpha n} \cdot (1-\alpha)^{(1-\alpha)n}} \\
	& = &	\frac{1}{\sqrt{2 \pi n \alpha (1 - \alpha)}} \cdot
		2^n \\
	& = &	\Theta\left(\frac{2^n}{\sqrt{n}}\right).
\end{eqnarray*}
}

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

\problem {\bf (24 points)} Shady finance people often assert that a
loan can be paid off more quickly by making half-size payments twice
as often.  The theory is that frequent payments prevent interest from
building up.  Suppose that I take out a loan for $L$ dollars, and at
the end of every month, the bank charges me interest on the loan at
rate $i$.

\begin{problemparts}

\problempart First, let's consider a ``frequent payment'' repayment
strategy.  Suppose that I pay $P$ dollars to the bank every month,
right after the bank charges me interest.  (So, after 1 month I owe $L
(1 + i) - P$ dollars, and after 2 months I owe $L (1 + i)^2 - P \cdot
(1 + i) - P$ dollars.)  Give a closed-form expression for the number
of months until the loan is repaid.

\bigskip

(Assume that interest charges are smaller than my monthly payment;
that is, $i L < P$.  Do not worry about rounding to an integral number
of months.)

\solution{
\textbf{Solution:}\\
After $k$ months, I owe

\begin{eqnarray*}
\lefteqn{L (1+i)^k - P \cdot (1+i)^{k-1} - P \cdot (1+i)^{k-2}
		- \ldots - P}
	\hspace{1in} \\
	& = &	L (1+i)^k - P \cdot \frac{(1+i)^k - 1}{i}.
\end{eqnarray*}

The loan is paid when the amount that I owe equals zero; that is, when

\begin{eqnarray*}
L (1+i)^k - P \cdot \frac{(1+i)^k - 1}{i} & = & 0.
\end{eqnarray*}

Solving for $k$, the number of months until the loan is repaid, gives

\begin{eqnarray*}
k & = &	\frac{\ln\left(\frac{P}{P-iL}\right)}{\ln(1 + i)}.
\end{eqnarray*}
}

\problempart Now let's consider an ``infrequent payment, late start''
repayment strategy.  Suppose that I pay $2P$ dollars to the bank every
two months, making the first payment two months after I take out the
loan.  (Thus, after 2 months I owe $L (1 + i)^2 - 2P$ dollars, and
after 4 months I owe $L (1+i)^4 - 2P \cdot (1 + i)^2 - 2P$ dollars.)
Give a closed-form expression for the number of months until the loan
in repaid.

\solution{
\textbf{Solution:}\\
After $k$ months, where $k$ is even, I owe

\begin{eqnarray*}
\lefteqn{L (1+i)^k - 2P \cdot (1+i)^{k-2} - 2P \cdot (1+i)^{k-4}
		- \ldots - 2P}
	\hspace{1in} \\
	& = &	L (1+i)^k - 2P \cdot \frac{(1+i)^k - 1}{(1+i)^2 - 1}.
\end{eqnarray*}

As before, the loan is repaid when the amount I owe equals zero.  This
happens when

\begin{eqnarray*}
k & = &	\frac{\ln\left(\frac{2P}{2P-((1+i)^2-1)L}\right)}{\ln(1 + i)}.
\end{eqnarray*}
}

\problempart Finally, let's consider an ``infrequent payment, early
start'' strategy.  As before, I pay $2P$ dollars to the bank every two
months, but now I make the first payment one month after I take out
the loan.  (Thus, after 1 month I owe $L (1 + i) - 2P$ dollars, and
after 3 months I owe $L (1 + i)^3 - 2P \cdot (1+i)^2 - 2P$ dollars.)
Give a closed-form expression for the number of months until the loan
is repaid.

\solution{
\textbf{Solution:}\\
After $k$ months, where $k$ is odd, I owe

\begin{eqnarray*}
\lefteqn{L (1+i)^k - 2P \cdot (1+i)^{k-1} - 2P \cdot (1+i)^{k-3}
		- \ldots - 2P}
	\hspace{1in} \\
	& = &	L (1+i)^k - 2P \cdot \frac{(1+i)^{k+1} - 1}{(1+i)^2 - 1}.
\end{eqnarray*}

The loan is repaid when

\begin{eqnarray*}
k & = &	\frac{\ln\left(\frac{2P}{2P(1+i)-((1+i)^2-1)L}\right)}{\ln(1 + i)}.
\end{eqnarray*}
}

\problempart Suppose that I take a loan of $L = \$100,000$.  The
monthly interest rate is $i = 0.005$.  I either pay the bank $P =
\$600$ every month or $2P = \$1,200$ every two months, depending on
the repayment strategy that I choose.  How long will repayment take
for each of the three strategies?

\solution{
\textbf{Solution:}\\
Substitution gives the following results:

\begin{tabular}{lcr}
frequent payment & \hspace{1in} & 360 months \\
infrequent payment, late start & & 362 months \\
infrequent payment, early start & & 356 months
\end{tabular}
}

\problempart In 50 words or fewer, explain the merits of frequent and
infrequent payment strategies.

\solution{
\textbf{Solution:}\\
Getting money to the bank early is more important than the
frequency of payments.}

\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
% problem 2, problem set 6, fall 1996

Find a closed-form expression for the summation
$\displaystyle\sum_{i=1}^n{i^2x^i}$.% and prove your answer is correct.

\solution{%
  %\begin{solution}
\textbf{Solution:}\\
    We first come up with a formula for ${\displaystyle \sum_{i=1}^n
      i^2x^i}$ and then prove it using induction. From class notes we
    know that:
    
    \[{\displaystyle \sum_{i=1}^n ix^i} = \frac{x - (n+1)x^{n+1} + nx^{n+2}}{(1-x)^2}.\] 

    Differentiating (with respect to $x$) the above expression and
    multiplying with $x$ we find that

    \[{\displaystyle \sum_{i=1}^n i^2x^i} = \frac{x+x^2-(n+1)^2x^{n+1}+(2n^2+2n-1)x^{n+2}-n^2x^{n+3}}{(1-x)^3}\]

    We prove that the above closed-form expression for the summation
    is correct by induction on the upper bound $n$ of the summation.
    In particular, let $P(n)$ be the predicate that:

    \[{\displaystyle \sum_{i=1}^n i^2x^i} = \frac{x+x^2-(n+1)^2x^{n+1}+(2n^2+2n-1)x^{n+2}-n^2x^{n+3}}{(1-x)^3}.\]

    Base Case. $P(1)$ is true since

    \[{\displaystyle \sum_{i=1}^1 i^2x^i} = x = \frac{x+x^2-4x^2+3x^3-x^4}{(1-x)^3}.\]

    Inductive Step. Assume $P(n)$ is true. Then
    \begin{eqnarray*}
      {\displaystyle \sum_{i=1}^n i^2x^i} + (n+1)^2x^{n+1} & = & \\
      {\displaystyle \sum_{i=1}^{n+1} i^2x^i} & = & \frac{x+x^2-(n+1)^2x^{n+1}+(2n^2+2n-1)x^{n+2}-n^2x^{n+3}}{(1-x)^3} + (n+1)^2x^{n+1} \\
      & = & \frac{x+x^2-(n+2)^2x^{n+2}+(2(n+1)^2+2(n+1)-1)x^{n+3}-(n+1)^2x^{n+4}}{(1-x)^3}
    \end{eqnarray*}

    Thus $P(n+1)$ is true. Hence, $P(n)$ is true for all $n$.
  %\end{solution}
  }

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

%\clearpage
\problem \textbf{Asymptotic notation}
% problem 1, problem set 7, fall 1999

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.

\vspace*{-0.5\baselineskip}

\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} &&&\\\hline
    2^n & 2^{n/2} &&&\\\hline
    \log(n!) & \log(n^n) &&&\\\hline
  \end{array}
\end{equation*}

\solution{
\textbf{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} & \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:\\
  (a) See notes on $O$-notation. (to appear)\\
  (b) Polynomial growth versus exponential growth. (See Theorem 3.6,
  Lecture 9, Fall97.)\\
  (c) When $n$ is a multiple of $\pi$, $n^{\sin n}=1$, so no
  constant times 1 will bound $\sqrt n$ as $n$ ranges over
  multiples of $\pi$. When $n$ is of the form $2k'\pi + \pi/2$,
  for some integer $k'$, then $n^{\sin n}=n$ and $\frac{n}{\sqrt n} =
  \sqrt n$ grows without bound as $k'$ increases.\\
  (d) $\frac{2^n}{2^{n/2}}=2^{n/2}$ grows without bound as $n$
  grows -- it is not bounded by a constant.\\
  (e) See Rosen \S 1.8 Ex. 61,62\\
  }

  \iffalse
  \problem \textbf{Asymptotic notation} \\
  You don't need to give proofs for this problem.

  \begin{problemparts}
    \problempart Find functions $f_1$, $f_2$, $g_1$, and $g_2$, such
    that
    \begin{align*}
      f_1(n) &= \Theta(f_2(n)),\\
      g_1(n) &= \Theta(g_2(n)),\\      
      \neg [f_1(g_1(n)) &= \Theta(f_2(g_2(n)))].\\
    \end{align*}

    \solution{$f_1(n) = f_2(n) = 2^n$, $g_1(n) = n$, $g_2(n) = 2n$.}
    

    \problempart Find functions $f$ and $g$ such that
    \begin{gather*}
      f(n) = O(g(n)), \text{ but } \neg [g(n) = O(f(n))];\\
      f(g(n)) = \Theta(g(f(n))).
    \end{gather*}

    \solution{$f(n) = n^2$, $g(n) = n^3$.}

      
    \problempart Find functions $f$ and $g$ such that
    \begin{alignat*}{3}
      f(n) &= O(g(n)), &\text{ but } &&\neg [g(n) &= O(f(n))];\\
      f(g(n)) &= O(g(f(n))),  &\text{ but } &&\neg [g(f(n)) &=
      O(f(g(n)))].\\
    \end{alignat*}

    \solution{$f(n) = n^2$, $g(n) = 2^n$.}
    
    
    \problempart Find functions $f$ and $g$ such that
    \begin{alignat*}{3}
      f(n) &= O(g(n)), &\text{ but } &&\neg [g(n) &= O(f(n))];\\
      g(f(n)) &= O(f(g(n))), &\text{ but } &&\neg [f(g(n)) &= O(g(f(n)))].\\
    \end{alignat*}
    
    \solution{$f(n) = 2^n$, $g(n) = 2^{2 n}$. Then $f(g(n)) = 2^{2^{2
          n}}$, while $g(f(n)) = 2^{2^{n+1}}$.}

  \end{problemparts}

\fi
  
\end{problems}
\end{document}






























