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

%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\pset{6}{October 17, 1995}{October 24, 1995}

{\bf Related Handouts:\  [MR] Chapter 5, [CLR] Chapters 2,3,4 .}

\bigskip

\begin{problems}

\problem
A college loan officer offers you the following deal.
He will give you \$25,000 at the start of each year for four years
starting today to pay for your college tuition.
In return, you must pay \$15,000 at the start of each year for fifteen years
starting in four years.  Suppose the annual interest rate is 5\%.
Is this a fair deal?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Find a closed form expression $f(n)$ for 
$\displaystyle\sum_{i=1}^n i^2 x^i$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Let $S_n = \sum_{i=1}^n \sqrt{i}$.  What is
$$\lim_{n \rightarrow \infty} \frac{S_n}{n^{1.5}} ?$$


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Use iteration to find a closed form expression for the recurrence
$$T(n) = aT(n/2) + bn$$ for $n>1$ and $T(1)=b$,
where $a$ and $b$ are constants.
You may assume $n$ is a power of $2$. 
Consider separately the cases $a<2$, $a=2$, and~$a>2$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Give tight asymptotic bounds ($\Theta$) for the following recurrences.
For each, $T(1)=1$.
\bparts
\ppart $T(n) = 3T\left(\floor{n\over 2}\right) + n^2$.
\ppart $T(n) = 2T\left(\floor{n\over 5}\right) + n$.
\ppart $T(n) = 4T\left(\floor{n\over 4}\right) + n$.
\ppart $T(n)=T\left(\floor{n\over 2}\right)+T\left(\floor{n\over 3}\right)+n$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\problem
Let $0< x < 1$ and $0 < y < 1$.  Evaluate the following infinite sums.
\bparts
\ppart $$\sum_{i=1}^{\infty} \sum_{j=1}^{\infty} x^i y^{i+2j}.$$
\ppart $$\sum_{i=1}^{\infty} \sum_{j=1}^{\infty} ij x^i y^j.$$
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Apparently, a standard model used by lobster fishermen is the following:
the number of lobsters caught in a given year is the average of the
number caught in the previous two years.  Let's try out this model
in the following hypothetical fishing community --- 
in year $0$, there were $100$ lobsters 
caught, and in year $1$, there were $300$ lobsters caught.  

\bparts
\ppart
Let $f(i)$ denote the number of lobsters caught in year $i$.
Write a recurrence relation for $f(i)$ and obtain a closed-form
solution.
\ppart
Now let's consider the following variation on this model: the number
of lobsters caught in a given year is the average of the number
caught in the previous {\em three} years.  To start things off,
suppose that $100$ were caught in year $0$, $300$ in year $1$, and
$200$ in year $2$.

Let $g(i)$ denote the number of lobsters caught in year $i$ under
this model.  Again, write a recurrence relation for $g(i)$ and 
obtain a closed-form solution.
\ppart
Finally -- let's go back to the model from the first part of this
question (just averaging the previous two years, with initial conditions $100$ lobsters in year $0$ and $300$ in year $1$).  But now there's
a new complication in our imaginary fishing village --- in year $i \geq 0$,
$i$ lobsters migrate into the fishing grounds from far-off waters, and
all of these new lobsters get caught as well.

Let $h(i)$ denote the number of lobsters caught in year $i$ under
this model.  Write a recurrence relation for $h(i)$ and obtain a
closed-form solution.  (\hint For the inhomogeneous part of your
solution, guess a function of the form $A i^2 + B i$.)

\eparts


\end{problems}

\end{document}

