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

\def\bparts{\begin{problemparts}}
\def\eparts{\end{problemparts}}
\def\ppart{\problempart}

\renewcommand{\reading}
{\href{http://theory.lcs.mit.edu/classes/6.042/spring02/handouts/lectures/ln5.pdf}
{Week 6 Notes}, Rosen \S1.7 thru Example 15; 1.8}
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

%\hidesolutions         
%\showsolutions

\begin{document}
\problemset{6}

% SOURCE:  FALL00, PSET 6

\begin{problem} 
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.  Let's analyze this.

Suppose that I take out a loan for $L$ dollars, and at the end of every
month, the bank charges me $m$\% monthly interest on the loan.
\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 $Ls -
P$ dollars, after 2 months I owe $(L s - P)s - P$ dollars, \etc, where $s
\eqdef 1 + m/100$.  Give a closed-form expression for the number
of months until the loan is repaid.

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

\solution{
After $k$ months, I owe
\[
L s^k - P \cdot s^{k-1} - P \cdot s^{k-2} - \cdots - P =
L s^k - P \cdot \frac{s^k - 1}{s-1}.
\]
The loan is paid when the amount that I owe equals zero; that is, when
\begin{eqnarray*}
L s^k - P \cdot \frac{s^k - 1}{s-1} & = & 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-(s-1)L}\right)}{\ln s}.
\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 s^2 - 2P$ dollars, and after 4 months I owe
$(L s^2 - 2P) s^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
\[
L s^k - 2P \cdot s^{k-2} - 2P \cdot s^{k-4} - \ldots - 2P = 
L s^k - 2P \cdot \frac{s^k - 1}{s^2 - 1}.
\]
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-(s^2-1)L}\right)}{\ln s}.
\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 s - 2P$ dollars, and after 3 months I
owe $(L s - 2P) s^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
\[
L s^k - 2P \cdot s^{k-1} - 2P \cdot s^{k-3}- \ldots - 2P =
L s^k - 2P \cdot \frac{s^{k+1} - 1}{s^2 - 1}.
\]
The loan is repaid when
\begin{eqnarray*}
k & = &	\frac{\ln\left(\frac{2P}{2Ps-(s^2-1)L}\right)}{\ln s}.
\end{eqnarray*}
}

\problempart Suppose that I take a loan of $L = \$100,000$.  The monthly
interest rate is $m = (1/2)\%$.  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{center}
\begin{tabular}{lcr}
frequent payment & \hspace{1in} & 360 months \\
infrequent payment, late start & & 362 months \\
infrequent payment, early start & & 356 months
\end{tabular}
\end{center}
}

\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{problem}


\begin{problem}
Suppose you deposit \$100 into your MIT Credit Union account
today, \$99 in one month from now, \$98 in two months from now, and so on.
Given that the interest rate is constantly 0.3\% per month, how long will
it take to save \$5,000?

\solution{
First note that you will certainly manage to have saved \$5,000
\emph{some} day, since, even without your earnings from the interest,
you will have $100+99+\cdots+1=100\times 101/2 = 5,050$ dollars after
99~months. 

But fewer months will be needed: After the first deposit you will have
\$100. After the second deposit, you will have \$$(100\times 1.003 +
99)$. After your third deposit, your saved money will be \$$\bigl(
(100\times 1.003 + 99)\times 1.003 + 98) =$ \$$\bigl( 100\times
(1.003)^2 + 99\times 1.003 + 98\bigr)$, and so on. So, after the $n$th 
deposit,  
$$
S_n = \sum_{i=0}^{n-1} (100 - i) (1.003)^{n-i-1}
$$
dollars will be in your account. Substituting $j=n-i-1$, we can
rewrite this as  
$$
\sum_{j=0}^{n-1} \bigl( 100 - (n-j-1)\bigr) (1.003)^{j};
$$
and then as 
$$
(101-n) 
\Bigl( \sum_{j=0}^{n-1} (1.003)^{j}   \Bigr)+
\Bigl( \sum_{j=0}^{n-1} j (1.003)^{j} \Bigr).
$$
Using the closed forms from Course Notes~6, we can finally write $S_n$
as 
\[
(101-n)
\Bigl( \frac{1-1.003^n}{1-1.003} \Bigr)+
\Bigl( \frac{1.003-n1.003^n+(n-1)1.003^{n+1}}{(1-1.003)^2} \Bigr).
\]
Solving 
$$
S_n \geq 5,000
$$ 
for $n$, we get $n\geq 67$. That is, you'll need more than 5.5~years
to save~\$5,000.
}
\end{problem}


% SOURCE: Spring01, PSET 5

\begin{problem}
\bparts

\ppart
Find a closed form solution for $\sum_{i=1}^n i^2x^i$.

\solution{
From Course Notes~6 we know that
\[
\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 two sides of the equation we have
\begin{equation*}
\sum_{i=1}^n i^2x^{i-1}  =
\frac{1+x-(n+1)^2x^{n}+(2n^2+2n-1)x^{n+1}-n^2x^{n+2}}{(1-x)^3}.
\end{equation*}
Then multiplying by $x$
\begin{equation*}
\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},
\end{equation*}
which is the closed form we were after.
}

\ppart Find a closed form formula for $\sum_{i=1}^n i^3$.
\solution{
One way to do this is by guessing that the solution is of the form
$a_4 n^4+a_3n^3+\cdots +a_1n+a_0$, then evaluating the sum at
$n=0,1,\dots,4$, then solving the resulting system of linear
equations for $a_4,a_3,\dots,a_0$, and finally checking by
induction that the resulting formula is correct. 

Here is another way: Start by noting that 
$$
k^4 - (k-1)^4 = 4k^3 - 6k^2 + 4k -1,
$$
and hence 
$$
k^3 = \tfrac{1}{4} \bigl( k^4 - (k-1)^4 + 6k^2 - 4k + 1 \bigr),
$$
for all $k\geq 1$. Summing both sides of this latter equation from~1
upto~n, we get 
\begin{align}
\nonumber
\sum_{k=1}^n k^3 
&= \sum_{k=1}^n \Bigl[
	\tfrac{1}{4} \bigl( k^4 - (k-1)^4 + 6k^2 - 4k + 1 \bigr)
   \Bigr]
\\ \label{eq:tocalc}
&= \tfrac{1}{4} \Bigl[ 
	\sum_{k=1}^n \bigl( k^4 - (k-1)^4 \bigr) + 
	6\sum_{k=1}^n k^2 - 
	4\sum_{k=1}^n k + 
	\sum_{k=1}^n 1 
   \Bigr].
\end{align}
Using the known facts
$$
\sum_{k=1}^n 1   = n, \qquad
\sum_{k=1}^n k   = \tfrac{1}{2}n(n+1), \qquad
\sum_{k=1}^n k^2 = \tfrac{1}{6}n(n+1)(2n+1),
$$
and the easy observation that the first of the right hand side sums
\emph{telescopes}, 
\begin{align*}
\sum_{k=1}^n \bigl( k^4 - (k-1)^4 \bigr)   
&= \sum_{k=1}^n k^4 - \sum_{k=1}^n (k-1)^4  \\
&= \sum_{k=1}^n k^4 - \sum_{k=0}^{n-1} k^4  \\
&= n^4 - 0^4                                \\
&= n^4,
\end{align*}
we conclude that Equation~\eqref{eq:tocalc} can be written as 
\begin{align*}
\sum_{k=1}^n k^3 
&= \tfrac{1}{4} [ n^4 + n(n+1)(2n+1) - 2n(n+1) + n ] \\
&= \tfrac{1}{4} [ n^4 + 2n^3 + n^2 ] \\
&= \tfrac{1}{4} n^2 [ n^2 + 2n + 1 ] \\
&= \tfrac{1}{4} n^2 (n + 1)^2 \\
&= \Bigl( \tfrac{ n(n + 1) }{2} \Bigr)^2.
\end{align*}
Note that this implies 
$\sum_{k=1}^n k^3 = \bigl( \sum_{k=1}^n k \bigr)^2$. Also note 
the standard general technique which we have applied here: To find a
closed form for $\sum_{k=1}^n k^a$, first express this sum in terms of 
\begin{itemize}
\item a telescoping sum of powers $a+1$ (which will always evaluate to
$n^{a+1}$), and
\item sums of smaller powers (which will always evaluate to
known closed forms);
\end{itemize}
then do the algebra to find the closed form you are after.
}
\eparts
\end{problem}



\begin{problem}
Use the integral method to find upper and lower bounds that differ by at
most 0.1 for the following sum
\iffalse
Note that you may need to add the first
few terms explicitly and then use integrals to bound the sum of the
remaining terms.
\fi
\[
\sum_{i=1}^{\infty} \frac{1}{i^2}.
\]

\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 bound the summation below 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*}
}
\noindent
(The actual value of the summation turns out to be $\pi^2 / 6 =
1.644\ldots$.)
\end{problem}


% SOURCE: FALL 00, Quiz 2
\begin{problem}
Determine which of the eight choices 
\[
\varTheta(n), \quad
\varTheta(n!), \quad
\varTheta(n\log n), \quad
\varTheta(n^2), \quad
\varTheta(1), \quad
\varTheta(2^n), \quad
2^{\gamma} \text{ for } \gamma(n) = \varTheta(n), \quad
\text{none of these}
\]
best describes each function's asymptotic behavior.  


\begin{problemparts}
\problempart  
\[
g(n) \eqdef n + \ln n + (\ln n)^2.
\]

\solution{
$\varTheta(n)$.
We know that 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) = 
\varTheta(n)$.  

Even better:
\[
\lim_{n\to \infty} \frac{g(n)}{n} =
\lim_{n\to \infty} \frac{n}{n} + \lim_{n\to \infty} \frac{\ln n}{n} +
 \lim_{n\to \infty} \frac{(\ln n)^2}{n}
= 1 + 0 + 0 = 1
\]
so in fact $g(n) \sim n$.
}

\problempart 
\[
h(n) \eqdef \frac{n^2 + 2n - 3}{n^2 - 1}.
\]

\solution{$\varTheta(1)$.
Dividing the top and bottom by $n-1$ yields $h(n) = (n+3)/(n+1)$.
Now, since the top is greater than the bottom, $h(n) > 1$ for all
$n\geq 0$.  Furthermore, solving the equation $(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) =
\varTheta(1)$. 

Even better:
\[
\lim_{n\to \infty} \frac{n^2 + 2n - 3}{n^2 - 1} = \lim_{n\to \infty}
 \frac{n^2 -1}{n^2 - 1} + \lim_{n\to \infty} \frac{2n}{n^2 - 1} +
 \lim_{n\to \infty} \frac{1-3}{n^2 - 1}
= 1 + 0 + 0 = 1
\]
so in fact $h(n) \sim 1$.
}

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

\solution{
$2^{\gamma}$.
Putting the summation in closed form yields $j(n) = (2/3)(4^{n+1}-1)$.

Now certainly, 
\[
\tfrac{2}{3}4^n \leq 
\tfrac{2}{3}(4^{n+1}-1) \leq
\tfrac{2}{3}4^{n+1}.
\]
Taking the base-2 logarithm of both sides, we get
\[
\lg\tfrac{2}{3} + \lg 4^n \leq 
\lg j(n) \leq
\lg\tfrac{2}{3} + \lg 4^{n+1},
\]
or
\[
(\lg 4)n + (1-\lg 3) \leq 
\lg j(n) \leq
(\lg 4)n + (3-\lg3).
\]
This clearly implies that $\lg j(n) \sim (\lg 4) n$ and $j(n) =
\varTheta(4^n)$.

Notice that because $4^n$ is \emph{not} $O(2^n)$, it is also \emph{not}
true that $j(n) =\varTheta(2^n)$.  So among the possible choices,
$2^{\gamma}$ for $\gamma=\varTheta(n)$ best describes the asymptotic
behavior of $j(n)$.
}

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

\solution{
$\varTheta(2^n)$.
We know that $\sin n \geq -1$ so $k(n) \geq (2-1)2^{n-1} = (1/2)2^n$.
We also know that $\sin n \leq 1$, so $k(n) \leq (2+1)2^{n+1} = 6\cdot2^n$.
Thus, $(1/2) 2^n \leq k(n) \leq 6\cdot2^n$, so $k(n) = \varTheta(2^n)$.
}

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

\solution{
None of the above.
By Stirling's approximation, we know that $f(n) = \varTheta(n^2 \ln n^2) =
\varTheta (n^2 \ln n)$.  Now, this grows faster than $\varTheta(1), \varTheta(n),
\varTheta(n^2)$ and $\varTheta(n \log n)$, and slower than
$\varTheta(n!), \linebreak[2] \varTheta(2^n)$ and $2^{\gamma}$,
so ``none of these'' is the correct answer. 
}
\end{problemparts}
\end{problem}


\end{document}                            


