%ARM 3/7 11:20pm

\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\usepackage{graphics}
\input{macros-course}

\begin{document}
\pset{5}{3/2/99 typo corrected 3/7}{Tuesday, March 9}
%\psol{5}{March 10, 1999}

\newcommand{\solution}[1]{}
%\newcommand{\solution}[1]{\bigskip #1}

\reading Sections 1.7 and 1.8 of Rosen and Fall 97 lecture notes.  In
section 1.7, skip the subsection on cardinality.

\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{ 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 \\
	& = &	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{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 (10 points)}  Let 
\[S_n ::= \sum_{k=1}^{n} 1/(2k-1) .\]

\bparts
\ppart Find a closed form expression for $S_n$ in terms of the harmonic
numbers $H_n$ and $H_{2n}$.

\ppart Use an approximation for the harmonic numbers to show that
\[
S_n = \ln(2 \sqrt{n}) + O(1).
\]

\solution{Recall that

\begin{eqnarray*}
H_n	& = &	\frac{1}{1}+\frac{1}{2}+\frac{1}{3} + \ldots +\frac{1}{n} \\
	& = &	\ln(n) + \gamma + o(1).
\end{eqnarray*}

where $\gamma = 0.577215\ldots$.  The sum in the problem can be
written as follows:

\begin{eqnarray*}
\sum_{k=1}^{n} \frac{1}{2k-1}
	& = &
\left(\frac{1}{1}+\frac{1}{2}+\frac{1}{3} + \ldots +\frac{1}{2n}\right) \\
	&   &	\mbox{} -
\left(\frac{1}{2}+\frac{1}{4}+\frac{1}{6} + \ldots +\frac{1}{2n}\right) \\
	& = &	H_{2n} - \frac{1}{2} \cdot H_{n} \\
	& = &	\ln(2n) + \gamma - \frac{1}{2} (\ln(n) - \gamma) + o(1) \\
	& = &	\ln\left(2 \sqrt{n}\right) + O(1)
\end{eqnarray*}
}
\eparts

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


\problem {\bf (10 points)} Use the integral method to find a $\Theta$
bound on the following sum.

\[
\sum_{i=1}^n i \ln i
\]

\solution{
We can bound the sum with two integrals.

\[
\int_1^n i \ln i \ di \ \leq \ 
	\sum_{i=1}^n i \ln i \ \leq \  
	\int_1^n (i+1) \ln(i+1) \ di
\]

Integration by parts gives the indefinite integral

\begin{eqnarray*}
\int i \ln i \ di
	& = &	\frac{1}{2} i^2 \ln i - \frac{1}{4} i^2 + C
\end{eqnarray*}

Substituting the appropriate integration ranges gives the bound
$\Theta(n^2 \ln n)$.}

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

\problem {\bf (20 points)} In analyzing algorithms, one often must
determine the asymptotic behavior of nasty functions like those
shown below.

\[
\begin{array}{ccc}
\iffalse \hspace{2cm} & n^{10} - n^{9} &\hspace{2cm} \fi
n! & (\ln n)^{300} & 2 n^{\ln \ln n}  \\
\iffalse  & \sum_{i=0}^n \sqrt{i}\fi
n^n & n (\ln n)^{4} & n^{1.01}/2 \\
7 n^2 + 3 & \sqrt{n}^{\sqrt{n}} & 4^n \\
\iffalse  & \frac{(2n)!}{n! \ n!}\fi
(n/e)^n & (7n^3 - 17n^2)/(n + 128) & (\ln n)^{\ln n}
\end{array}
\]

Arrange these functions in a list so that each is $\Theta$ or $O$ of
the next function in the list.  For each pair of consecutive functions
in your list, indicate whether the stonger $\Theta$ relationship holds
or only the weaker $O$ relationship.  No proofs are required.

\solution{
\begin{eqnarray*}
(\ln n)^{300}		& = & O\left(n (\ln n)^{4}\right) \\
n (\ln n)^{4}		& = & O\left(\frac{1}{2} n^{1.01}\right) \\
\frac{1}{2} n^{1.01}	& = & O\left(\sum_{i=0}^n \sqrt{i}\right) \\
\sum_{i=0}^n \sqrt{i}	& = & O\left(7 n^2 + 3\right) \\
7 n^2 + 3		& = & \Theta\left(\frac{8n^3 - 17n^2}
					{n + 128}\right) \\
\frac{8n^3 - 17n^2}
	{n + 128}	& = & O\left(n^{10} - n^{9}\right) \\
n^{10} - n^{9}		& = & O\left((\ln n)^{\ln n}\right) \\
(\ln n)^{\ln n}		& = & \Theta\left(2 n^{\ln \ln n}\right) \\
2 n^{\ln \ln n}		& = & O\left(\sqrt{n}^{\sqrt{n}}\right) \\
\sqrt{n}^{\sqrt{n}}	& = & O\left(\frac{(2n)!}{n! \ n!}\right) \\
\frac{(2n)!}{n! \ n!}	& = & O\left(4^n\right) \\
4^n			& = & O\left(\left(\frac{n}{e}\right)^n\right) \\
\left(\frac{n}
	{e}\right)^n	& = & O\left(n!\right) \\
n!			& = & O\left(n^n\right)
\end{eqnarray*}
}

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

\problem {\bf (10 points)}

Recently, David Bowie, a British music star, sold a portion of the
future profits from his music for \$55 million dollars to Prudential
Insurance.  This deal spawned others.

\begin{problemparts}

\problempart Billy Joel wants to sell his future profits for \$200
million today.  Suppose that he can generate a fixed profit at the end
of every year for the next 20 years.  If the inflation rate is $p =
0.03$, how large must Billy Joel's annual profit be for investors to
make a $10\%$ return?

\solution{Suppose that Billy Joel makes $M$ dollars at the end of
every year for the next 20 years.  Then his contract is worth

\begin{eqnarray*}
\sum_{i=1}^{20} \frac{M}{(1+p)^i}
	& = &	\frac{M}{1+p} \cdot \sum_{i=0}^{19} \frac{1}{(1+p)^i} \\
	& = &	\frac{M}{1+p} \cdot
		\frac{\left(\frac{1}{1+p}\right)^{20} - 1}
			{\frac{1}{1+p} - 1} \\
	& = &	M \cdot 14.877\ldots.
\end{eqnarray*}

To make his contract worth \$200 million + 10\%, Billy Joel must make
$M \approx \$14.7$ million in profit every year.}

\problempart The Eagles figure that they can generate at least \$25
million from their music at the end of each year for eternity.  What
should an investor who wants a 15\% return pay today for the Eagles
contract?

\solution{Let $M = \$25,000,000$.  The Eagles are worth

\begin{eqnarray*}
\sum_{i=1}^{\infty} \frac{M}{(1+p)^i}
	& = &	\frac{M}{1+p} \cdot \frac{1}{1 - \frac{1}{1+p}} \\
	& = &	\frac{M}{p}
\end{eqnarray*}

Since the investor wants a 15\% return, he should pay

\begin{eqnarray*}
\frac{M}{1.15p}	& \approx &	\$724 \text{ million}
\end{eqnarray*}
}

\end{problemparts}

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

\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{
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{
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{
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{
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{Getting money to the bank early is more important than the
frequency of payments.}

\end{problemparts}

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

\end{problems}

\end{document}
