\documentclass[12pt]{article}
\input{macros-course}

\askaboutsolutions

\begin{document}

\ifshowsolutions
  \psetsol{7}{October 26, 2001}{\stamp}
\else
  \pset{7}{October 15, 2001}{Wednesday 10/24, beginning of lecture}{\stamp}
\fi

\ifshowsolutions
{} %
\else
\emph{You MUST include a \textbf{collaboration statement} and your
\textbf{TA's name} on the first page of your solutions.}
\fi

\textbf{Reading:} Lecture Notes 7. Rosen \S1.7 through Example 15; \S1.8

\begin{problems}

% Fall 1998   PSET 4

\iffalse
\section{Annuities}

\problem 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?

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

\fi
\problem %spring00 ps5

Suppose you were about to enter college today and a college loan
officer offered you the following deal: \$25,000 at the start of each
year for four years to pay for your college tuition and an option of
choosing one of the following repayment plans:

\begin{description}\itemsep 0\baselineskip
\item[Plan A:] Wait four years, then repay \$$20,000$ at the start of
  each year for the next ten years.
\item[Plan B:] Wait five years, then repay \$$30,000$ at the start of
  each year for the next five years.
\end{description}

Suppose the annual interest rate is currently 7\% and does not change
in the future.  

\begin{itemize}\itemsep 0\baselineskip
\item[a)] Which repayment plan would you choose?

\solnospace{  
The use of the word `interest' above is slightly awkward. It refers to
the additional money you (or the loan officer) would make if your money
was just sitting in a bank. However, we can treat it just as we treat
inflation: $\$1$ today will be worth $\$1.07$ next year, and $\$1.07^2$ the
year after.

 Given this, set $r = \cfrac{1}{1.07}$. Then:
 
\begin{eqnarray*}
A & = & \sum_{y=0}^{9} 20000 \cdot r^{y+4}  \\
  & = & r^4 \cdot \sum_{y=0}^{9} 20000 \cdot r^y  \\
  & = & 20000r^4 \cdot \sum_{y=0}^{9} r^y \\
  & = & 20000r^4 \cdot \frac{1 - r^{10}}{1 - r} \\
  & = & \$114,666.9
\end{eqnarray*}

\begin{eqnarray*}
B & = & \sum_{y=0}^{4} 30000 \cdot r^{y+5}  \\
  & = & r^5 \cdot \sum_{y=0}^{4} 30000 \cdot r^y  \\
  & = & 30000r^5 \cdot \sum_{y=0}^{4} r^y \\
  & = & 30000r^5 \cdot \frac{1 - r^{5}}{1 - r} \\
  & = & \$93,840.63
\end{eqnarray*}

You should clearly take Plan B. You will be paying back much less in today's
dollars.}

\item[b)] What is the loan officer's effective profit (in today's
  dollars) on the loan?

\solnospace{
The value of the money you are given is:
\begin{eqnarray*}
Loan & = & \sum_{y=0}^{3} 25000 \cdot r^{y}  \\
  & = & 25000 \cdot \sum_{y=0}^{3} r^y \\
  & = & 25000 \cdot \frac{1 - r^{4}}{1 - r} \\
  & = & \$90,607.90
\end{eqnarray*}

Therefore, the loan officer's profit is effectively $\$3,233$. (Or 
$\$24,059$ if we are not on the ball).
}

\end{itemize}


\iffalse
\problem S01 pset 5, prob 7
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.  Suppose that I take out a loan for $L$ dollars, and at
the end of every month, the bank charges me interest on the loan at
rate $i$.

\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 $L
(1 + i) - P$ dollars, and after 2 months I owe $L (1 + i)^2 - P \cdot
(1 + i) - P$ dollars.)  Give a closed-form expression for the number
of months until the loan is repaid.

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

\solnospace{
After $k$ months, I owe

\begin{eqnarray*}
\lefteqn{L (1+i)^k - P \cdot (1+i)^{k-1} - P \cdot (1+i)^{k-2}
		- \ldots - P}
	\hspace{1in} \\
	& = &	L (1+i)^k - P \cdot \frac{(1+i)^k - 1}{i}.
\end{eqnarray*}

The loan is paid when the amount that I owe equals zero; that is, when

\begin{eqnarray*}
L (1+i)^k - P \cdot \frac{(1+i)^k - 1}{i} & = & 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-iL}\right)}{\ln(1 + i)}.
\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 (1 + i)^2 - 2P$ dollars, and
after 4 months I owe $L (1+i)^4 - 2P \cdot (1 + i)^2 - 2P$ dollars.)
Give a closed-form expression for the number of months until the loan
in repaid.

\solnospace{
After $k$ months, where $k$ is even, I owe

\begin{eqnarray*}
\lefteqn{L (1+i)^k - 2P \cdot (1+i)^{k-2} - 2P \cdot (1+i)^{k-4}
		- \ldots - 2P}
	\hspace{1in} \\
	& = &	L (1+i)^k - 2P \cdot \frac{(1+i)^k - 1}{(1+i)^2 - 1}.
\end{eqnarray*}

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-((1+i)^2-1)L}\right)}{\ln(1 + i)}.
\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 (1 + i) - 2P$ dollars, and
after 3 months I owe $L (1 + i)^3 - 2P \cdot (1+i)^2 - 2P$ dollars.)
Give a closed-form expression for the number of months until the loan
is repaid.

\solnospace{
After $k$ months, where $k$ is odd, I owe

\begin{eqnarray*}
\lefteqn{L (1+i)^k - 2P \cdot (1+i)^{k-1} - 2P \cdot (1+i)^{k-3}
		- \ldots - 2P}
	\hspace{1in} \\
	& = &	L (1+i)^k - 2P \cdot \frac{(1+i)^{k+1} - 1}{(1+i)^2 - 1}.
\end{eqnarray*}

The loan is repaid when

\begin{eqnarray*}
k & = &	\frac{\ln\left(\frac{2P}{2P(1+i)-((1+i)^2-1)L}\right)}{\ln(1 + i)}.
\end{eqnarray*}
}

\problempart Suppose that I take a loan of $L = \$100,000$.  The
monthly interest rate is $i = 0.005$.  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?

\solnospace{
Substitution gives the following results:

\begin{tabular}{lcr}
frequent payment & \hspace{1in} & 360 months \\
infrequent payment, late start & & 362 months \\
infrequent payment, early start & & 356 months
\end{tabular}
}

\problempart In 50 words or fewer, explain the merits of frequent and
infrequent payment strategies.

\solnospace{Getting money to the bank early is more important than the
frequency of payments.}

\end{problemparts}
\fi

%\section{Sums}

\iffalse
\problem\pts{10} \textbf {Bounding Infinite Sums}
Fall 2000 Quiz 2 (not multiple choice, but could be)

Using the Integral Method, give an upper bound for 
\[\sum_{i=1}^n \frac{3}{i^{10}} \] 

\solnospace{
Since $f(k)=\frac{3}{i^{10}}$ is monotonically decreasing for $x>1$, we have:
\begin{eqnarray*}
\sum_{i=1}^n{\frac{3}{i^{10}}} &=& 3 + \sum_{i=2}^n{\frac{3}{i^{10}}} \\
&\leq& 3+ \int_1^n{\frac{3}{x^{10}}}dx\\
&=& 3+ 3\int_1^n{\frac{1}{x^{10}}}dx\\
&=& 3 + 3\left [{\frac{-1}{9x^{9}}}\right ]_1^n\\
&=& 3 + \left [{\frac{-1}{3x^{9}}}\right ]_1^n\\
&=& 3 - \frac{1}{3n^{9}} + \frac{1}{3}\\
&=& \frac{10}{3} - \frac{1}{3n^{9}}
\end{eqnarray*}
Hence, $\sum_{i=1}^n \frac{3}{x^{10}} \leq \frac{10}{3} - \frac{1}{3n^{9}}$.

}
\fi



\problem %Fall 2000 Quiz 2

Find a simplified closed form for each of the expressions listed below.

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

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

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

\solnospace{
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

%pset5 problem9 spring98
\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}} \]

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

%\section{Asymptotic Notation}

\iffalse
\problem{\bf[9 points]}  Quiz 1 Fall97

For each of the following pairs of functions $f(n)$ and $g(n)$, fill
in the blank with $o$, $O$, $\omega$, $\Omega$, and $\Theta$ depending 
on whether $f(n)=o(g(n))$, $f(n)=O(g(n))$, $f(n)=\omega(g(n))$,
$f(n)=\Omega(g(n))$, or $f(n)=\Theta(g(n))$.
If there is more than one relation between $f(n)$ and $g(n)$, write
the strongest one. You do not need to supply any proofs.  

\begin{eqnarray*}
n^2                 & = & n^3\\
2^n                 & = & 3^n\\
\log_2 n            & = & \log_3 n\\
n^3		     & = & 2^n\\
\frac{n}{\log n}     & = & n\\
\log_2 n             & = & \sqrt n\\
8^{\log_2  n}        & = & n^{\log_2 8}\\
(n!)^2               & = & n^n \\
2^{\log_3 n}         & = & n^2
\end{eqnarray*}

\solnospace{\begin{eqnarray*}
n^2                 & = & o (n^3)\\
2^n                 & = & o (3^n)\\
\log_2 n            & = & \Theta (\log_3 n)\\
n^3		     & = & o (2^n)\\
\frac{n}{\log n}     & = & o (n)\\
\log_2 n             & = & o (\sqrt n)\\
8^{\log_2  n}        & = & \Theta  (n^{\log_2 8})\\
(n!)^2               & = & \omega (n^n) \\
2^{\log_3 n}         & = & o  (n^2)
\end{eqnarray*}
}
\fi

\iffalse
\problem\pts{25} \textbf {Asymptotic Notation}  Fall 2000 Quiz 2

Determine which of the eight choices below best describes each
function's asymptotic behavior.  No proofs are necessary.  {\bf (5
points each)}

\begin{tabbing}
XXX\=XXXXXXXXXXXX\=\kill
\>$\theta (n)$\>$\theta (n!)$\\
\>$\theta (n\log n)$\>$\theta (n^2)$\\
\>$\theta (1)$\>$\theta (2^n)$\\
\>$2^{\theta(n)}$\>None of the above
\end{tabbing}

\problempart  $g(n) = n + \ln n + (\ln n)^2$.

\solnospace{\bigskip
$\theta(n)$

We know that for sufficiently large $n$, $n > (\ln n)^2 > \ln n$.  
(For instance, if $n > e^2$ then $(\ln n)^2 = 4 < e^2$.)  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) = 
\theta(n)$.  
}


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

\solnospace{
$\theta(1)$

Dividing the top and bottom by $n-1$ yields

$h(n) = \frac{n+3}{n+1}$.  

Now, since the top is greater than the bottom, $h(n) > 1$ for all $n > -1$.
Furthermore, solving the equation $\frac{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) = \theta(1)$.
}

\problempart $j(n) = \sum_{i = 0}^n 2^{2i+1}$

\solnospace{
$2^{\theta(n)}$

Putting the summation in closed form yields $j(n) = 2(4^n)/3$.

Now certainly, $\log_2 j(n) = \log_2(2/3) + n\log_2(4) = \theta(n)$.  Thus, 
$j(n) = 2^{\theta(n)}$.  However, as we showed in tutorial, $\neg (4^n = 
O(2^n))$ so $\neg (j(n) = \theta(2^n))$.  So $2^{\theta(n)}$ best 
describes
the asymptotic behavior of $j(n)$. 
}

\problempart $k(n) = (2 + \sin (n))2^{n + \sin(n)}$.

\solnospace{
$\theta(2^n)$

We know that $\sin n \geq -1$ so $k(n) \geq (2-1)2^{n-1} = \frac122^n$.

We also know that $\sin n \leq 1$ so $k(n) \leq (2+1)2^{n+1} = 6\cdot2^n$.

Thus, $\frac12 2^n \leq k(n) \leq 6\cdot2^n$, so $k(n) = \theta(2^n)$.
}

\problempart $f(n) = \ln ((n^2)!)$.

\solnospace{None of the above.

By Stirling's approximation, we know that $l(n) = \theta(n^2 \ln n^2) =
\theta (n^2 \ln n)$.  Now, this grows faster than $\theta(1), \theta(n),
\theta(n^2)$ and $\theta(n \log n)$, and slower than $\theta(n!),
\theta(2^n)$ and $2^{\theta(n)}$, so ``none of these'' is the correct
answer. 

}
\fi

\problem \textbf{Asymptotic notation}

For each pair of functions $(f(n), g(n))$ in the table below, indicate
whether the statement at the top of the column is true (e.g., whether
$f(n) = O(g(n))$).  Assume $k\geq 1$, $\epsilon > 0$, and $c > 1$ are
constants. Your answer should be in the form of a table with ``yes'' or
``no'' in each box.
\begin{equation*}
\begin{array}{|cc|*{3}{c|}}
\hline
f(n) & g(n) & f(n) = O(g(n)) & g(n) = O(f(n)) & f(n) = \Theta(g(n)) \\\hline\hline
\log^k n & n^\epsilon &&&\\\hline
n^k & c^n &&&\\\hline
\sqrt{n} & n^{\sin n\pi/2} &&&\\\hline
2^n & 2^{n/2} &&&\\\hline
\log(n!) & \log(n^n) &&&\\\hline
\end{array}
\end{equation*}

\solnospace{
\newcommand\y{\text{yes}}
\newcommand\n{\text{no}}

\begin{equation*}
\begin{array}{|cc|*{3}{c|}}
\hline
f(n) & g(n) & f(n) = O(g(n)) & g(n) = O(f(n)) & f(n) =
\Theta(g(n)) \\\hline\hline
\log^k n & n^\epsilon & \y & \n & \n \\\hline
n^k & c^n & \y & \n & \n \\\hline
\sqrt{n} & n^{\sin n\pi/2} & \n & \n & \n\\\hline
2^n & 2^{n/2} & \n & \y & \n \\\hline
\log(n!) & \log(n^n) & \y & \y & \y \\\hline
\end{array}
\end{equation*}

Following are some hints on deriving the table above:\\ \iffalse (a) See
notes on $O$-notation. (to appear)\\ \fi

Row:

(2) Polynomial growth versus exponential growth. (See Theorem 7.6, Notes
7.)

(3) $n^{\sin n\pi/2}=1$ for even values of $n$.  So no constant times
$n^{\sin n\pi/2}$ will be an upper bound on $\sqrt n$ as $n$ ranges over
even numbers.  When $n \equiv 1 \bmod 4$, then $n^{\sin n\pi/2}= n^1 =n$,
so no constant times $\sqrt n$ will be an upper bound on $n^{\sin n\pi/2}$
as $n$ ranges over numbers $\equiv 1 \bmod 4$.

(4) $\cfrac{2^n}{2^{n/2}}=2^{n/2}$ grows without bound as $n$ grows -- it
is not bounded by a constant.

(5) See Rosen \S 1.8 Ex. 61,62 }

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

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

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

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

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

\iffalse
\problem Prove the following statement: If $f$ and $g$ are
positive-valued functions such that $f(n) = \Theta(g(n))$, and
$\lim_{n\to\infty} g(n) = \infty$, then $\log f(n) \sim \log g(n)$
(the base of the logarithm is arbitrary).

\solnospace{     
We have,
\begin{equation*}
\frac{\log f(n)}{\log g(n)} =
\frac{\log g(n) -\log g(n) + \log f(n)}{\log g(n)}
= \frac{\log g(n) + \log \frac{f(n)}{g(n)}}{\log g(n)}
= 1 + \frac{\log \frac{f(n)}{g(n)}}{\log g(n)}
\end{equation*}
We are given that $f(n)=\Theta(g(n))$, therefore
$\lim_{n\to\infty}\frac{f(n)}{g(n)}$ is bounded (away from 0, as
otherwise $\lim_{n\to\infty}\frac{g(n)}{f(n)}$ would be unbounded
i.e. $g\neq O(f)$), and moreover,
$\lim_{n\to\infty}\log\frac{f(n)}{g(n)}$ is bounded. We are also
given that $\lim_{n\to\infty} g(n) = \infty$, therefore
$\lim_{n\to\infty} \log g(n) = \infty$. Thus, 
\begin{equation*}
\lim_{n\to\infty} \frac{\log f(n)}{\log g(n)} =
\lim_{n\to\infty} (1 + \frac{\log \frac{f(n)}{g(n)}}{\log g(n)})
= 1 + \frac{\lim_{n\to\infty}\log
\frac{f(n)}{g(n)}}{\lim_{n\to\infty} \log g(n)}
= 1.
\end{equation*}
i.e. $\log f(n) \sim \log g(n)$.}


\problem {\bf (12 points)} Fall 1998 Final exam

Find a closed-form expression for $T(N)$ in
each problem part.  Your answer may make use of $\Theta$ notation.  No
proofs are required.

\begin{problemparts}

\problempart {\bf (6 points)}

\begin{eqnarray*}
T(n)    & = &   \sum_{i=1}^n \frac{i^2 + 6 \sqrt{i}}{i \sqrt{i}}
\end{eqnarray*}

\solnospace{
\begin{eqnarray*}
T(n)    & = &   \sum_{i=1}^n \frac{i^2 + 6 \sqrt{i}}{i \sqrt{i}} \\
& = &   \sum_{i=1}^n \frac{i^2}{i \sqrt{i}} +
\sum_{i=1}^n \frac{6 \sqrt{i}}{i \sqrt{i}} \\
& = &   \sum_{i=1}^n \sqrt{i} +
\sum_{i=1}^n \frac{6}{i} \\
& = &   \Theta\left(n^{3/2} + \ln n\right) \\
& = &   \Theta\left(n^{3/2}\right)
\end{eqnarray*}
}

\problempart {\bf (8 points)} Fall 2000 Final exam

Circle the numbers of ALL of the
following functions which are $\theta(n)$:

1.  $f(n) = 8000 \sqrt{n} + .00034 n$\\
2.  \[g(n) = \frac{n^2 + 3n - 4}{-4n^2 + 9n + 9}\]
3.  $h(n) = \log (n!/n)$\\
4.  $l(n) = n^{1 + \frac{1}{n}}$

\solnospace{
1 and 4 are $\theta(n)$.

1: $f(n)$ is clearly $\theta(n)$ since the growth of $n$ outstrips
that of $\sqrt{n}$.

2: $g(n)$ is $O(n)$ but not $\Omega(n)$ since $\lim_{n \to \infty}
g(n) = -\frac14$.

3: $h(n)$ is $\Omega(n)$ but not $O(n)$.  By Stirling's approximation,
$\log(n!) = \theta(n \log n)$.  Thus, $h(n) = \theta (n \log n - n)$ which
is still $\theta(n \log n)$.

4: $l(n)$ is clearly greater than $n$, so it is $\Omega(n)$.  However, the
other direction is harder.  The question becomes whether there is a constant
$c$ such that for sufficiently large $n$,

$$n^{1 + \frac1n} < cn$$
$$n^{\frac1n} < c$$
$$\frac1n \log n < \log c$$

which is true for (say) $c = e$ since $\lim_{n \to \infty} \frac1n \log n = 0$.
Thus, $l(n) = O(n)$, so $l(n) = \theta(n)$.
}

\end{problemparts}

\fi


\iffalse
\problem
Give an example of functions $f,g:\naturals\to\naturals$ such that neither
$f = O(g)$ nor $g = O(f)$.  Prove it.

\solution{
\textbf{Solution:} $f(n) = 1 + n(n \bmod 2), g(n) =1 + n ((1 + n) \bmod 2)$.
So $f(n)$ is $n$ times the size of $g(n)$ on odd $n$, vice-versa on even
$n$.
}


\problem Prove or give a counterexample:
If $f_1,f_2,\dots$ is a sequence of functions from $\naturals$ to
$\naturals$ such that $f_i(n) = O(1)$ for all $i\geq 1$, then 
\[\sum_{i=1}^n f_i(n) = O(2^n).\]

\solution{
\textbf{Solution:} False, let $f_i$ be a constant function with $f(n) =
b(i)$ for all $n$, where $b(i)$ is nonnegative and not $O(2^i)$, for
example, $b(i) = i2^i$.  So $f_i = O(1)$ for each $i$.  Now
\[\sum_{i=1}^n f_i(n) \geq f_n(n) = b(n) \neq O(2^n).\]
}
\fi

\problem

Regrouping or reordering the terms of an infinite series is ok for
\emph{absolutely convergent} series, namely, series for which the sum of
the absolute values of their terms converges.

In other cases, rearranging terms is not ok.
An extreme example is
\[
S \eqdef \sum_{i=0}^{\infty} (-1)^i = 1 + (-1) + 1 + (-1) + \cdots
\]
because by regrouping the terms we can deduce:
\begin{eqnarray*}
S & = & [ 1 + (-1) ] + [ 1 + (-1) ] + \cdots = 0 + 0 + \cdots = 0,\\
S & = & 1 + [(-1) + 1] + [(-1) + 1] + \cdots = 1 + 0 + 0 + \cdots = 1.
\end{eqnarray*}

To see the problem here, let $S_n \eqdef \sum_{i=0}^{n}(-1)^i$.  Then $S_n
= 1$ for odd $n$ and $S_n = 0$ for even $n$.  Hence $S_n$ does not have a
well-defined limit as $n$ tends to infinity, implying that $S$ is not a
convergent series.

Even for convergent, but not absolutely convergent, series, rearranging
terms can cause big changes.  For example, the series
\[
1 - 1/2 + 1/3 - 1/4 \dots
\]
converges, but is not absolutely convergent.

Explain how to reorder terms in $1 - 1/2 + 1/3 - 1/4 \dots$, so that the
resulting series converges to 3.  \dots so it converges to 4.  \dots so it
doesn't converge.

\solnospace{
Note that the sum of the negative terms goes to negative infinity, because
the sum
\[
-1/2 - 1/4 - 1/6 -  \dots - 1/2n = -H_n/2 \sim (-\ln n)/ 2
\]
and $\ln n$ goes to infinity with $n$.  Similarly, the sum of the positive
terms goes to positive infinity.

To reorder the terms to converge to 3, begin by taking the positive terms
in decreasing order until their sum first exceeds 3.  Next, take the
negative terms in order of decreasing magnitude until the sum of all the
terms taken---positive and negative---first goes below 3.  Now take the
remaining positive terms in decreasing order until the sum again exceeds 3,
then the negative terms till the sum goes below 3, and so on.  It is always
possible to move the sum above or below 3 by taking enough of the remaining
positive or negative terms, because the remaining positive terms sum to
positive infinity and the remaining negative terms sum to negative
infinity.  Also, the running sum of the positive and negative terms taken
in this way goes above and below 3 at most by the magnitude of the last
term taken.  Since the magnitude of the terms goes to zero, this implies
that the sum goes above and below 3 by an amount that decreases to zero.
But this is exactly what it means to say the sum converges to 3.

Replacing ``3'' by ``4'' above yields an ordering in which the sum
converges to 4.

Finally, alternately taking enough positive terms to increase the sum by 1
and then taking one negative term, yields an ordering in which the sum
diverges to positive infinity.

This argument applies to \emph{any} convergent series that is not
absolutely convergent to show that it can be reordered to converge to
\emph{any} desired number, or to diverge.  The moral: when reordering terms
in a series, be sure to check for absolute convergence.

}

\end{problems}

\end{document}                            
