\documentstyle[12pt,epic,eepic,twoside,macpsfig,amssymb]{article}
\input{macros-course}
%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\psol{6}{October 26, 1995}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Present value of what the college loan officer offers
\begin{eqnarray*}
 & = & 25000 + 25000/1.05 + 25000/(1.05)^2 + 25000/(1.05)^3 \\
 & = & 25000(1 - \frac{1}{(1.05)^4})/(1 - \frac{1}{1.05}) \\
 & = & 25000 * 3.72\\
 & = & \$93,081.20
\end{eqnarray*}

Present value of what you must pay in return 
\begin{eqnarray*}
 & = & 15000/(1.05)^4 + 15000/(1.05)^5 + \ldots + 15000/(1.05)^{18} \\
 & = & (15000/(1.05)^4)(1 - \frac{1}{(1.05)^{15}})/(1 - \frac{1}{1.05}) \\
 & = & 15000 * 8.97\\
 & = & \$134,495.08
\end{eqnarray*}

So this is not quite a fair deal for you. Of course, in reality the
loan officer must charge a premium for default risk.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
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}\]

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
We use the integral method for bounding $S_n$. 
\[ \int_1^{n+1}\sqrt{x}dx \geq S_n \geq \int_0^n \sqrt{x}dx.\]
i.e.
\[\frac{(2/3)((n+1)^{3/2} - 1)}{n^{3/2}} \geq \frac{S_n}{n^{3/2}} \geq \frac{(2/3)n^{3/2}}{n^{3/2}}\]
Taking limits as $n \rightarrow \infty$ we find that
\[2/3 \geq {\displaystyle \lim_{n \rightarrow \infty}\frac{S_n}{n^{3/2} }} \geq 2/3\]

i.e. ${\displaystyle \lim_{n\rightarrow\infty}\frac{S_n}{n^{3/2}}} = 2/3.$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
\begin{eqnarray*}
T(n) & = & aT(n/2) + bn \\
     & = & a^2T(n/2^2) + abn/2 + bn \\
     & = & \ldots \\
     & = & a^iT(n/2^i) + bna^{i-1}/2^{i-1} +  bna^{i-2}/2^{i-2} +\ldots + bn \\
     & = & \ldots \\
     & = & a^{\log_2n}T(1) + bn(1 + a/2 + (a/2)^2 + \ldots + (a/2)^{\log_2n-1})
\end{eqnarray*}

Case 1. $a < 2$. Then it is easy to see from the above that 
\begin{eqnarray*}
T(n) & = & a^{\log_2n}T(1) + bn(1 + a/2 + (a/2)^2 + \ldots + (a/2)^{\log_2n-1}) \\
 & = & n^{\log_2a}T(1) + n\Theta(1)\\
 & = & \Theta(n)
\end{eqnarray*}

Case 2. $a = 2$. Then it is easy to see from the above that 
\begin{eqnarray*}
T(n) & = & a^{\log_2n}T(1) + bn(1 + a/2 + (a/2)^2 + \ldots + (a/2)^{\log_2n-1}) \\
 & = & nT(1) + bn\log_2n \\
 & = & \Theta(n\log_2n)
\end{eqnarray*}

Case 3. $a > 2$. Then it is easy to see from the above that 
\begin{eqnarray*}
T(n) & = & a^{\log_2n}T(1) + bn(1 + a/2 + (a/2)^2 + \ldots + (a/2)^{\log_2n-1}) \\
 & = & n^{\log_2a}T(1) + bn((a/2)^{\log_2n}-1)/((a/2)-1) \\
 & = & \Theta(n^{\log_2a})
\end{eqnarray*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
\bparts
\ppart 
Using iteration we find $T(n) = 3^{\log_2n}T(1) + n^2(1 + 3/2^2 +
(3/2^2)^2 + \ldots + (3/2^2)^{\log_2n-1}) = n^{\log_23}T(1) +
n^2\Theta(1) = \Theta(n^2)$.
\ppart
It is clear that $T(n) = \Omega(n)$. We show by induction that $T(n) =
O(n)$ thus proving that $T(n) = \Theta(n)$. To do this, we show that
$\exists$ a constant $c$ such that $\forall n, T(n) \leq cn$. We pick
$c = 2$. Let $P(n)$ be the statement that $T(n) \leq cn$.\\
Base Case. $T(1) = 1 \leq 2\cdot 1.$ Hence  $P(1)$ is true. \\
Induction Step. Assume $P(k)$ is true for all $k \leq n$. Then 
\begin{eqnarray*}
T(n+1) & = & 2T(\lfloor \frac{n+1}{5} \rfloor) + (n+1) \\
        & \leq & 2\cdot 2\cdot(\lfloor\frac{n+1}{5} \rfloor) + (n+1) \\
        & \leq & 4n/5 + (n+1) \\
	& \leq 2(n+1)
\end{eqnarray*}
(We made use of the inductive hypothesis to infer that $T(\lfloor
\frac{n+1}{5} \rfloor) \leq 2\cdot(\lfloor\frac{n+1}{5} \rfloor)$.)
Thus we have proved $P(n+1)$. Hence $P(n)$ is true for all $n$. 
\ppart
Using iteration we find that $T(n) = 4^{\log_4n}T(1) + n\log_4n =
\Theta(\log n).$
\ppart
It is clear that $T(n) = \Omega(n)$. We show by induction that $T(n) =
O(n)$ thus proving that $T(n) = \Theta(n)$. To do this, we show that
$\exists$ a constant $c$ such that $\forall n, T(n) \leq cn$. We pick
$c = 12$. Let $P(n)$ be the statement that $T(n) \leq cn$.\\
Base Case. $T(1) = 1 \leq 12\cdot 1.$ Hence  $P(1)$ is true. \\
Induction Step. Assume $P(k)$ is true for all $k \leq n$. Then 
\begin{eqnarray*}
T(n+1) & = & T(\lfloor \frac{n+1}{2} \rfloor) + T(\lfloor \frac{n+1}{3} \rfloor) + (n+1) \\
        & \leq & 12\cdot(\lfloor\frac{n+1}{2} \rfloor) +  12\cdot(\lfloor\frac{n+1}{3} \rfloor) + (n+1) \\
        & \leq & 6(n+1) + 4(n+1) + (n+1) \\
	& \leq 12(n+1)
\end{eqnarray*}
(We made use of the inductive hypothesis to infer that $T(\lfloor
\frac{n+1}{2} \rfloor) \leq 12\cdot(\lfloor\frac{n+1}{2} \rfloor)$ and $T(\lfloor
\frac{n+1}{3} \rfloor) \leq 12\cdot(\lfloor\frac{n+1}{3} \rfloor)$ .)
Thus we have proved $P(n+1)$. Hence $P(n)$ is true for all $n$.
\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
\bparts
\ppart
\begin{eqnarray*}
{\displaystyle \sum_{i=1}^\infty \sum_{j=1}^\infty x^iy^{i+2j}} & = & {\displaystyle (\sum_{i=1}^\infty (xy)^i) (\sum_{j=1}^\infty (y^2)^j)} \\
 & = & (xy/(1-xy))\cdot (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)} \\
 & = & (x/(1-x)^2)\cdot (y/(1-y)^2) \\
 & = & (xy)/((1-x)(1-y))^2
\end{eqnarray*}
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
\bparts
\ppart
\[f(i) = (1/2)(f(i-1) + f(i-2))\]
This is a homogenous linear recurrence. We solve the characteristic
equation, $2x^2 -x - 1 = 0$, to get the roots $1$ and $-1/2$. Hence
the general solution is of the form $f(i) = A + B(-1/2)^i$. Using the
boundary conditions $f(0) = 100$ and $f(1) = 300$ we find that the
general solution is $f(i) = 700/3 - (400/3)(-1/2)^i$.
\ppart
\[g(i) = (1/3)(g(i-1) + g(i-2) + g(i-3))\]
This is a homogenous linear recurrence. We solve the characteristic
equation, $3x^3 -x^2 - x - 1 = 0$, to get the roots $1$,
$\frac{-1-\sqrt{-2}}{3}$ and $\frac{-1+\sqrt{-2}}{3}$. Hence the
general solution is of the form $g(i) = A +
B(\frac{-1-\sqrt{-2}}{3})^i + C(\frac{-1+\sqrt{-2}}{3})^i$. Using the
boundary conditions $g(0) = 100$, $g(1) = 300$ and $g(2) = 200$ we
find that the general solution is $g(i) = 650/3 +
(-25/3)(7-4\sqrt{-2})(\frac{-1-\sqrt{-2}}{3})^i +
(-25/3)(7+4\sqrt{-2})(\frac{-1+\sqrt{-2}}{3})^i$.
\ppart
\[h(i) = (1/2)(h(i-1) + h(i-2)) + i\]
For the homogenous part we get the same characteristic equation as in
part a). Hence the homogenous solution is of the form $C +
D(-1/2)^i$. We guess a particular solution of the form $Ai^2+Bi$,
plug into the recurrence and equate coefficients of like powers on
both sides, to get $A = 1/3$ and $B=5/9$. Now we use the boundary
conditions $h(0) = 100$ and $h(1) = 300$ to find that the general
solution is $h(i) = 6284/27 + (-3584/27)(-1/2)^i + (1/3)i^2 + (5/9)i$.
\eparts

\end{problems}

\end{document}





