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

%% FALL04 Pset 4.  Compiled by C. Monteleoni. Sources cited below.

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

%\hidesolutions         
%\showsolutions
\fi

\begin{document}
\problemset{6}

%% Word problems: summations (finance).

%source FALL01 PS7
\begin{problem} 
\begin{problemparts}
\problempart A banker loans \$100,000 to the Addams
family so that they can purchase a new dilapidated mansion.  At the
end of each year for the next 20 years, Morticia Addams will drop by
the bank to make a payment on the loan.  The banker will immediately
invest this returned money at a 7\% annual rate of return.

What annual payment should the banker require of the Addams family so
that his return after 20 years is the same as if he had invested the
whole amount at 7\% today instead of making the loan?

\solution{
Suppose that Morticia pays $p$ dollars at the end of each year for 20
years.  The banker can invest the first payment for 19 years, the
second payment for 18 years, etc.  Therefore, after 20 years his total
cash is:

\begin{eqnarray*}
\sum_{i=0}^{19} p \cdot 1.07^i
	& = &	p \cdot \sum_{i=0}^{19} 1.07^i \\
	& = &	p \cdot \frac{1.07^{20} - 1}{1.07 - 1}
\end{eqnarray*}

The second equation uses the formula for the sum of a finite
geometric series.

On the other hand, if the banker invests the money at 7\% today, then
after 20 years his total cash is $100,000 \cdot 1.07^{20}$.

Equating these two expressions and solving for $p$, Morticia's annual
payment, we find:

\begin{eqnarray*}
p \cdot \frac{1.07^{20} - 1}{1.07 - 1}
	& = & 100,000 \cdot 1.07^{20} \\
p	& = &	100,000 \cdot 1.07^{20} \cdot
		\frac{1.07 - 1}{1.07^{20} - 1} \\
	& \approx & \$9439.29
\end{eqnarray*}
}

\end{problemparts}
\end{problem}

%source Spring02 PSET 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}

\iffalse

%% Summations, non-word problems
%% Two problems listed, but first is quite long.  Could eliminate a problem or part.

%% SOURCE: Spring01 PS5
\begin{problem}
Find closed-form expressions for the following sums.

\begin{problemparts}
\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*}
}

\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 \\
    & = &   n (n+1)
\end{eqnarray*}
}


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

%% SOURCE FALL01 PS7
\begin{problem}
Find a simplified closed form for each of the expressions listed below.

\bparts
\problempart $ \sum_{i=x}^{y} 2i+1 $

\solution{
There are two ways of doing this problem.  In the first, we re-form the 
sum so the lower limit is 0 instead of $x$ and apply the arithmetic sum 
formula.  

$$\sum_{i=x}^y 2i+1 = \sum_{i=0}^{y-x} 2(i+x)+1$$
$$= \sum_{i=0}^{y-x} 2i + 2x+1$$
$$= (y-x+1)(2x+1) + 2 \sum_{i=0}^{y-x} i $$
$$= (y-x+1)(2x+1) + 2 \frac{(y-x)(y-x+1)}{2} $$
$$= (y-x+1)(2x+1 + y-x) = (y-x+1)(y+x+1) = ((y+1)-x)((y+1)+x) $$
$$= (y+1)^2 - x^2.$$


In the second, we express this sum as the difference of two summations,
one involving only $y$ and one involving only $x$.  
$$
\sum_{i=x}^{y} 2i+1 = \sum_{i=0}^{y} 2i + 1 - (\sum_{i=0}^{x-1} 2i +
1).
$$
Now, since 

$$\sum_{i=0}^n 2i+1 = n+1 + 2\frac{n(n+1)}{2} = n+1 + n(n+1) = n^2 +
2n+1 = (n+1)^2,$$

we can evaluate this to

$$(y+1)^2 - x^2.$$
}

\problempart
${\displaystyle \sum_{i=0}^{\infty} \sum_{j=1}^n \left(\cfrac{j}{j+2}\right)^i}$

\solution{
First, we reorder the summations to get

$$\sum_{j=1}^n \sum_{i=0}^{\infty} \left(\frac{j}{j+2}\right)^i.$$

We can do this reordering because the value of $j$ never depends on the
value of $i$, we just use every possible pair of values for a nonnegative 
$i$ and a $j$ between 1 and $n$.

Evaluating the inner summation, which is just an infinite geometric
series, we get

$$\sum_{j=1}^n \cfrac{1}{1 - \cfrac{j}{j+2}}$$
$$= \sum_{j=1}^n \cfrac{j+2}{2}$$
$$= n + \frac{1}{2}\sum_{j=1}^n j$$
$$= n + \cfrac{n(n+1)}{4}$$

which simplifies to $\frac{1}{4}n^2 + \frac{5}{4}n$.

}

\ppart ${\displaystyle \prod_{i=1}^n 2 \cdot 4^i}$.

\solution{
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}$
}

\eparts
\end{problem}
\fi


%% Integral meth for approximating sums
% SOURCE FALL01 PS7
%pset5 problem9 spring98
\begin{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}} \]

\solution{
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, 
\[
\lim_{n\rightarrow\infty}\frac{S_n}{n^{4/3}} = 3/4.
\]
}

\end{problem}


% Source Spring02 PS6
\begin{problem}
Use the integral method to find upper and lower bounds that differ by at
most 0.1 for the following sum.  (Note that you may need to add the first
few terms explicitly and then use integrals to bound the sum of the
remaining terms.)

\[
\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*}
}

The actual value of the summation turns out to be $\pi^2 / 6 =
1.644\ldots$.
\end{problem}


%% Harmonic numbers, and applications
% Source Spring01 PS6
\begin{problem}

In this problem we will estimate the \emph{average} number of
divisors a ``typical'' number has.  More precisely, let $a(n)$ denote
the average number of divisors of the numbers from $1$ to $n$.
\begin{problemparts}
\ppart Let $f_{ij}=1$ if $i \mid j$, and 0 otherwise.  Explain why
\begin{displaymath}
  a(n) = \frac{1}{n} \sum_{j=1}^n \sum_{i=1}^n f_{ij}
\end{displaymath}

\solution{
For a fixed~$j$, $\sum_{i=1}^n f_{ij}$ is
  the number of divisors of~$j$.}

\ppart For a given~$i$, what is the value of $\sum_{j=1}^n f_{ij}$?

\solution{ $\lfloor n/i \rfloor$.}

\ppart Give a closed form estimate of $a(n)$ that is accurate to
within plus or minus 2 for any~$n$.

\solution{
 By the solution above,
  \begin{displaymath}
    a(n) =
    \frac{1}{n} \sum_{j=1}^n \sum_{i=1}^n f_{ij} =
    \frac{1}{n} \sum_{i=1}^n \sum_{j=1}^n f_{ij} =
    \sum_{i=1}^n \frac{\lfloor n/i \rfloor}{n}\,.
  \end{displaymath}
  Since
  \begin{displaymath}
    \frac{n-i}{i} \leq \biggl\lfloor\frac{n}{i}\biggr\rfloor \leq 
    \frac{n}{i}\,
  \end{displaymath}
  we obtain the bound
  \begin{displaymath}
    \sum_{i=1}^n \biggl(\frac{1}{i} - \frac{1}{n}\biggr) \leq
    a(n) \leq
    \sum_{i=1}^n \frac{1}{i}\,,
  \end{displaymath}
  or, equivalently, $H_n - 1 \leq a(n) \leq H_n$, where $H(n)$~denotes
  the $n$th harmonic number. From the lecture notes, we now the bound
  $\ln(n+1) \leq H_n \leq \ln n + 1$. Combining these bounds, we obtain
  \begin{displaymath}
    \ln(n+1) - 1 \leq a(n) \leq \ln n + 1.
  \end{displaymath}
}

\end{problemparts}

\end{problem}


%% SOURCE Spring02 cp6w
\begin{problem}
\textbf{INSERT DESERT-CROSSING METHOD FROM SLIDES.}

\bparts

\ppart Conclude that a truck can travel across any size desert if there
is a large enough gas depot at the border of the desert.

\ppart Notice that a truck can also make a \emph{round trip} across any
size desert -- simply by using the one-way strategy for a desert of twice
the length and turning around whenver it reaches the far border.
However, using a strategy similar to the one-way strategy, but tailored
for the round trip, the truck can do better.  Describe such a round trip
strategy and show that it is asymptotically better than the ``turn
around'' version of the one-way strategy. 

\solution{
Let $R_n$ be the distance a truck can travel into the desert \emph{and
return} on $n$ tanks of gas.  Clearly, $R_1 = 1/2$.

On $n+1$ tanks, the truck will travel distance $x$ and back $n$ times,
leaving $1-2x$ tanks of gas at distance $x$ into the desert on each trip.
It then makes one more one-way trip to $x$.  This leaves it with $n(1-2x)
+ 1-x$ tank of gas at position $x$.  Leaving an $x$th of a tank so it can
get back, if the remaining $(n(1-2x) + 1-x) -x = (n+1)(1-2x)$ tanks equal
$n$, it can execute the $n$-tank round trip strategy from position $x$ and
still return to the desert border.  So
\begin{eqnarray}
(n+1)(1-2x) & = & n\\
x & = & 1/2(n+1)\\
R_{n+1} & = & R_n + x = R_n + 1/2(n+1).
\end{eqnarray}
So
\[
R_n = 1/2 (1 + 1/2 + 1/3 + \cdots + 1/n) = H_{n}/2.
\]

\textbf{COMPARE TO ONE-WAY TURN-AROUND METHOD.}
}
\eparts

\end{problem}

%% Big-Oh, Big-theta, etc

%% SOURCE FALL01: PS7

\begin{problem}
\textbf{Asymptotic notation} \\
You don't need to give proofs for this problem.

\begin{problemparts}
\problempart Find functions $f_1$, $f_2$, $g_1$, and $g_2$, such
that
\begin{align*}
f_1(n) &= \Theta(f_2(n)),\\
g_1(n) &= \Theta(g_2(n)),\\      
\neg [f_1(g_1(n)) &= \Theta(f_2(g_2(n)))].\\
\end{align*}

\solution{$f_1(n) = f_2(n) = 2^n$, $g_1(n) = n$, $g_2(n) = 2n$.}


\problempart Find functions $f$ and $g$ such that
\begin{gather*}
f(n) = O(g(n)), \text{ but } \neg [g(n) = O(f(n))];\\
f(g(n)) = \Theta(g(f(n))).
\end{gather*}

\solution{$f(n) = n^2$, $g(n) = n^3$.}


\problempart Find functions $f$ and $g$ such that
\begin{alignat*}{3}
f(n) &= O(g(n)), &\text{ but } &&\neg [g(n) &= O(f(n))];\\
f(g(n)) &= O(g(f(n))),  &\text{ but } &&\neg [g(f(n)) &=
O(f(g(n)))].\\
\end{alignat*}

\solution{$f(n) = n^2$, $g(n) = 2^n$.}


\problempart Find functions $f$ and $g$ such that
\begin{alignat*}{3}
f(n) &= O(g(n)), &\text{ but } &&\neg [g(n) &= O(f(n))];\\
g(f(n)) &= O(f(g(n))), &\text{ but } &&\neg [f(g(n)) &= O(g(f(n)))].\\
\end{alignat*}

\solution{$f(n) = 2^n$, $g(n) = 2^{2 n}$. Then $f(g(n)) = 2^{2^{2
n}}$, while $g(f(n)) = 2^{2^{n+1}}$.}
\end{problemparts}
\end{problem}

% source Spring02 PSET 6
% 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}


\iffalse

%% Stirlings approx for n!
%% Note:  this already appears in a big-theta prob above, so just adding one prob here.

%SOURCE: Spring01 Tut8

\begin{problem}           
In how many ways can $2n$ students be divided into $n$ pairs?
Investigate the asymptotic behavior of your answer.

\solution{

$\displaystyle \frac{(2n)!}{n! 2^n} = 
\sqrt{2}\left(\frac{2n}{e}\right)^n(1 + o(1))$

Consider all the ways of ordering the $2n$ students in a line. There are
$(2n)!$ ways of doing this. Now group them into pairs based on the
linear order, i.e. group the first and second students, group the third
and fourth students, \ldots, group the $(2n-1)$th and $2n$th students. Thus
each linear order gives us a unique grouping into pairs. But observe
that two different linear orders could give rise to the same grouping
into pairs. So let us now count the number of linear orders that give
rise to the same grouping into pairs. Given a grouping into pairs, to
generate a linear order we need to order each pair (there are $2^n$
ways to do this) and then order the $n$ pairs (there are $n!$ ways to
do this). Hence $n! 2^n$ linear orders give the same grouping into
pairs. Thus the total number of ways $2n$ students can be divided into
$n$ pairs is $\frac{(2n)!}{n! 2^n}$.
Using Stirling's formula on this expression gives
\begin{displaymath}
  \frac{(2n)!}{n! 2^n}
  = 
  \frac{(2n)^{2n} e^{-2n}\sqrt{4\pi n} (1 + o(1))}
  {n^n e^{-n}\sqrt{2\pi n} (1 + o(1)) 2^{n}}
  =
  \sqrt{2}\left(\frac{2n}{e}\right)^n(1 + o(1)).
\end{displaymath}
}
\end{problem}
\fi


\end{document}                            


