\documentstyle[12pt,twoside,amstex]{article}
\input{macros-course}

\begin{document}
\psol{5}{March 9, 1998}


\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 1
\problem 

A college loan officer offers prospective M.Eng students the following
deal.  He will give them \$23,100 at the start of each year for five years
starting today to pay for their college tuition.  He offers the following
plan for repayment:\\
Wait five years, then repay \$$x.00$ at the start
of each year for the next ten years.

Suppose the annual interest rate is 8\%.  What value of $x$ will make the 
present value of the repayment equal to the present value of the loan?


\bigskip
The formula for finding the present value of an annuity (given in lecture)
is
\[V = m \sum_{j=0}^{n-1}{1 \over (1+p)^j}\]
where $V$ is the present value, $m$ is the dollar amount of each payment, $n$ is
the number of years of the annuity, and $p = 0.08$ is the current
interest rate.

So the present value of what the college loan officer offers is
\begin{eqnarray*}
V & = & 23100 \cdot {\displaystyle\sum_{j=0}^4(\frac{1}{1+p})^j} \\
 & = & 23100 \cdot {\displaystyle\frac {(1 - \frac{1}{(1 + p)^5})} {(1 -
 \frac{1}{1 + p})}} \\
 & = & 23100 \cdot 4.312\\
 & = & \$99,610.13.
\end{eqnarray*}

The value, $V'$, of the repayment is
\[V' = x \cdot \sum_{j=5}^{14} \frac{1}{(1+p)^j}.\]

Since we want the present values to be equal, let $V' = V$, and solve for
$x$:
\begin{eqnarray*}
x & = & {\$99,610.13 \over { (\frac{1}{1+p})^5} \cdot (\sum_{j=0}^9(\frac{1}{1+p})^j) }\\
 & = & \frac {\$99,610.13} { (\frac{1} {1+p})^5 \cdot { {(1 - \frac{1}{(1+p)^{10}})} \over {(1 - \frac{1}{1+p})}}}\\
 & = & \frac  {\$99,610.13}{0.6805 \cdot 7.246}\\
 & = & \$20,196.25.
\end{eqnarray*}

So, rounding off to the nearest dollar, $x=\$20, 196$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2 (Rosen 1.7, 11 and 12)

\problem 


\bparts
\ppart Find a closed form solution for \[\sum_{k=1}^n {1
/k(k+1)}\] \hint Use the fact that ${1 / k(k+1)}=1 / k - 1 / (k+1)$.


\bigskip
We will use the fact that
\[\sum_{j=0}^{n-1} (a_j-a_{j+1}) = a_0 - a_n,\]
where $a_0, a_1, ..., a_n$ is a sequence of real numbers.  (This type of
sum is called {\em telescoping}, for obvious reasons).  This holds almost
by inspection: we can say that the $-a_{j+1}$ in one term of the summation
will be the $a_j$ in the subsequent term, and the only $a_j$'s that don't
cancel out in this manner are $a_0$, since there is no term before
$(a_0-a_1)$ in the summation, and $a_n$, since there is no term after
$(a_{n-1}-a_{n})$ in the summation.
Formally, this equation can be verified by an easy induction which
we omit.

Now (to get back to the problem at hand), using the given hint, 
$$\sum_{k=1}^n {1 \over {(k(k+1))}} = \sum_{k=1}^n {{1 \over k} - {1 \over {(k+1)}}}$$
Letting $a_i=\frac{1}{i+1}$, for $0\leq i \leq n-1$, the righthand sum above is
$$\sum_{i=0}^{n-1} (a_i - a_{i+1}) = a_0-a_n.$$
Now
\begin{eqnarray*}
a_0-a_n & = & {1 \over{0+ 1}} - {1 \over {n+1}} \\
&=& 1- {1 \over {n+1}}\\
&=& {n \over {n+1}}.
\end{eqnarray*}
\ppart Use induction to verify your closed form.
\bigskip


Proof by induction. Let $P(n)$ be the statement that 
$$\forall n>1, \sum_{k=1}^n {1 \over {(k(k+1))}} = {n \over {n+1}}$$

Base Case. P(1) is true since
$$\sum_{k=1}^1 {1 \over {(k(k+1))}}={ 1 \over 2} = { 1 \over {1+1}}$$.

Inductive Step. Assume $P(n)$ is true. Then
\begin{eqnarray*}
\sum_{k=1}^{n+1} {1 \over {(k(k+1))}} &=&{1 \over {(n+1)((n+1)+1)}}  +  \sum_{k=1}^n {1 \over {(k(k+1))}}\\
&=& {1 \over {(n+1)(n+2)}}  + {n \over {n+1}}\\
&=&{ {n^2+2n+1} \over {(n+1)(n+2)}}\\
&=&{ {(n+1)^2} \over {(n+1)(n+2)}}\\
&=&{ {n+1} \over {((n+1)+1)}}\\
\end{eqnarray*}
Therefore by induction, 
$$\forall n>1, \sum_{k=1}^n {1 \over {(k(k+1))}} = {n \over {n+1}}$$
\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 3
\problem 

Find a closed form solution for $\prod_{i=1}^n 2 \cdot 4^i$.

\bigskip


We know that $\prod_{i=1}^n 2 \cdot 4^i =(2\cdot4^1) \cdot (2\cdot4^2) \cdot ... \cdot (2\cdot4^n).$
Taking $\log_2$ of both sides of the equation gives us
\begin{eqnarray*}
\log_2(\prod_{i=1}^n 2\cdot4^i)&=&\log_2(2\cdot4^1 \cdot 2\cdot4^2 \cdot ... \cdot 2\cdot4^n)\\
&=&\log_2(2\cdot4^1)+\log_2(2\cdot4^2)+...+\log_2(2\cdot4^n)\\
&=&\sum_{j=1}^n\log_2(2\cdot4^j)\\
&=&\sum_{j=1}^n(\log_2(2) + \log_2(4^j))\\
&=&\sum_{j=1}^n (1 +  2j)\\
&=&n+n(n+1)\\
&=&n^2+2n.
\end{eqnarray*}
Now, exponentiating both sides of the equation gives
$\prod_{i=1}^n 2\cdot4^i=2^{n^2+2n}$


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 4
%solution from F95 PS6, revised
\problem 

 	Let $0< x < 1$ and $0 < y < 1$.  Evaluate the following infinite sums.
\bparts
\ppart 

\begin{eqnarray*}
\sum_{i=1}^\infty \sum_{j=1}^\infty x^iy^{i+2j}
 & = &  \sum_{i=1}^\infty [(xy)^i (\sum_{j=1}^\infty (y^2)^j)] \\
 & = &  \sum_{i=1}^\infty [(xy)^i (y^2/(1-y^2))]\\
 & = &  [\sum_{i=1}^\infty (xy)^i] y^2/(1-y^2)\\
 & = & [xy/(1-xy)] y^2/(1-y^2) \\
 & = & (xy^3)/(1-xy)(1-y^2).
\end{eqnarray*}


\ppart
\begin{eqnarray*}
{\displaystyle \sum_{i=1}^\infty \sum_{j=1}^\infty ijx^iy^j} & = & {\displaystyle \sum_{i=1}^\infty [ix^i (\sum_{j=1}^\infty jy^j)]} \\
 & = & {\displaystyle [\sum_{i=1}^\infty ix^i] (\sum_{j=1}^\infty jy^j)} \\
 & = & [x/(1-x)^2] y/(1-y)^2 \\
 & = & (xy)/((1-x)(1-y))^2
\end{eqnarray*}


\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 5
\problem
Justify your answers to the following:
\bparts
\ppart Is $2^n$ $O(4^n)$? 

Yes, $2^n=O(4^n)$. To show this, we need to find an $n_0$ and a $c$ that
satisfy the definition of $O$, specifically,
$\forall n>n_0, 2^n<c \cdot 4^n$.
Choose $n_0=0$ and $c=1$. Then we have
$\forall n>0, 2^n<4^n$, which is certainly true.

\ppart Is $2^{2n}$ $O(2^n)$? 

$2^{2n}$ is not $O(2^n)$.
To prove that $2^{2n}=O(2^n)$, we
have to find an $n_0$ and $c$ for which
$\forall n>n_0, 2^{2n}<c \cdot 2^n$.
Let's divide both sides by $2^n$, which we can do since $2^n$ is
always positive, and never equal to $0$. Then we have 
$\forall n>n_0, 2^n<c$.
Since $2^n$ is unbounded as $n \rightarrow \infty$, there's
no $n_0$ for which $2^n$ will be less than a constant.

\ppart Is $2^{n+1}$ $O(2^n)$?

Yes, $2^{n+1}=O(2^n)$, with (for example) $c=2$, and $n_0=0$.

\ppart Is $\log_{10}x=\Theta(\log_2x)$?

Yes.
The change of base formula tells us that
$\log_an={{\log_cn} \over {\log_c a}}$.
Therefore, we know that $\log_{10} n = {{\log_2n} \over {\log_2 10}}$.
For all $n>0$, $\log_{10} n$ is within a constant factor, namely ${1 \over {\log_2 10}}$, of $\log_2 n$.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 6
\problem 

Find a $\Theta$ bound for $\sum_{k=1}^n k^6$.

\bigskip
Let $\sum_{k=1}^n k^6 = S_n$.

There are $n$ terms in $S_n$ and each term is at most $n^6$, so 
$S_n \leq n \cdot n^6 = n^7 = O(n^7)$. So $S_n=O(n^7)$.

On the other hand, at least $(n-1)/2$ of the terms are as large as $[(n-1)/2]^6$, 
so 
\begin{eqnarray*}
S_n &\geq & ((n-1)/2) \cdot [(n-1)/2]^6\\
    & = & [(n-1)/2]^7 \\
    & \geq & (n/3)^7
\end{eqnarray*}
for $n>3$,  so $n^7 \leq 3^7 \cdot S_n$. In other words, $n^7 = O(S_n)$. Since we've shown $S_n=O(n^7)$ and $n^7 = O(S_n)$, we know that  $S_n = \Theta(n^7)$.


We can also do this problem using the Integral Method:

\begin{eqnarray*}
\int_0^n x^6 \ dx \leq \sum_{k=1}^n k^6 \leq \int_0^n (x+1)^6 \ dx \\
\frac{n^7}{7} \leq \sum_{k=1}^n k^6 \leq \frac{(n+1)^7}{7} - \frac{1}{7}
\end{eqnarray*}

From which we see that  $\sum_{k=1}^n k^6 = \Theta(n^7)$



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 7
\problem 

Prove or give a counterexample: If $f(n) = \Theta(n)$, then $\sum_{i=1}^n f(i)
= \Theta(n^2)$.

If $f(n) = \Theta(n)$, we know that $\exists c_1, c_2, k >0$, such that
$\forall n>k, c_1n\leq f(n)\leq c_2n$.  Let's assume that $n > 2k$.  (Note
that we can make assumptions of this type since we're free to choose the
lower bound on $n$ needed in the definition of the $\Theta$ bound that
we're proving.  That is, we're going to prove that $a_1n^2 \leq
\sum_{i=1}^n f(i) \leq a_2 n^2$ for all $n>n_0$, and we can make the $n_0$
as large as we'd like.)

Let's look at $\sum_{i=k+1}^n c_1 i$.  Since $n > 2k$, at least ${n \over 2}$ terms in the sum must be bigger than $c_1 {n \over 2}$, which we can state mathematically as follows:

\begin{eqnarray*}
({n \over 2})^2 \cdot c_1 & \leq & \sum_{i=k+1}^n c_1 i \\
& \leq &  \sum_{i=k+1}^n f(i)\\  %from the fact that f(i)=\Theta(n) 
& \leq &  \sum_{i=k+1}^n c_2 i \\
& \leq &  \sum_{i=k+1}^n c_2 n \\
& \leq & c_2 n^2.
\end{eqnarray*}

So, $${c_1 \over 4} n^2 \leq \sum_{i=k+1}^n f(i) \leq c_2n^2$$
Now we need to manipulate this to get the summation to start at
$1$, rather than $k+1$. (Note that the definition of $\Theta$ will only
let us assume that $c_1n \leq f(i) \leq c_2n$ for $i>k$, so we need
to find some other method of dealing with the sum from $1$ to $k$).

Let $s=\sum_{i=1}^{k}f(i)$. Then, by adding $s$ to each part of
the inequality above, we get
$${c_1 \over 4}n^2 + s \leq \sum_{i=1}^n f(i) \leq c_2n^2 + s$$

Now, assume that $n \geq \sqrt{\abs {s}}$, so we can write
$c_2n^2+s \leq (c_2+1)n^2$ 

Assume $n \geq \sqrt{ 8\abs {s}/c_1}$, so ${\displaystyle {c_1 \over 8}n^2 \leq {c_1 \over 4}n^2 +s}$

So, letting $n_0 = max(2k, \sqrt{\abs s}, \sqrt{8 \abs{s} / c_1})$, we now
know that for all $n>n_0$,
\[{c_1 \over 8}n^2 \leq {c_1 \over 4}n^2 + s \leq \sum_{i=1}^n f(i) \leq
c_2n^2+s \leq (c_2+1)n^2,\]
which satisfies the definition of $\Theta(n^2)$, with
$a_1={c_1 \over 8}, a_2=c_2+1$. \qed
                                     

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 8
%solution from F95 PS6 solutions, revised
\problem 
\bparts
\ppart Find a closed form solution for
$\sum_{i=1}^n i^2x^i$.

From lecture 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 
\begin{eqnarray*}
{\displaystyle \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}\\
{\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}
\end{eqnarray*}

\ppart Verify your closed form by induction.

Proof by induction. Let $P(n)$ be the statement 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+1} i^2x^i}
& = & {\displaystyle \sum_{i=1}^n i^2x^i} + (n+1)^2x^{n+1} \\
 & = & \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$.
\eparts



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 9
\problem
Let $S_n = \sum_{i=1}^n i^{1 /3}$.  Use the integral method to determine
\[\lim_{n \rightarrow \infty} \frac{S_n}{n^{4 / 3}} \]

We use the integral method for bounding $S_n$. 
\[\int_0^n x^{\frac{1}{3}}dx \leq S_n \leq \int_1^{n+1}x^{\frac{1}{3}}dx.\]
That is,
\[\frac{(3/4)n^{4/3}}{n^{4/3}}  \leq \frac{S_n}{n^{4/3}} \leq   \frac{(3/4)((n+1)^{4/3} - 1)}{n^{4/3}}\]
Taking limits as $n \rightarrow \infty$ we find that
\[3/4 \leq {\displaystyle \lim_{n \rightarrow \infty}\frac{S_n}{n^{4/3} }} \leq 3/4\]

Therefore, ${\displaystyle \lim_{n\rightarrow\infty}\frac{S_n}{n^{4/3}}} = 3/4.$

\end{problems}

\end{document}

