\documentstyle[12pt,macpsfig,psfig,amssymb]{article}
\input{macros-course}
 
\addtolength{\topmargin}{-.2in}
\setlength{\textheight}{9in}
 
\setcounter{page}{0}
 
\begin{document}
 
\qsol{2}{November 18, 1996}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%1
\problem (10 points)\\

Give tight ($\Theta$) bounds for 
$$ \sum_{i=1}^n \frac{1}{\sqrt{i}}$$\\
You do not need to prove your answer formally, but you should show how you
derived it.\\


We use the integration method for bounding summations.\\
\begin{eqnarray*}
{\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} \\
{\displaystyle 2x^{\frac{1}{2}}|_1^n} & \leq  {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle 2x^{\frac{1}{2}}|_1^n} \\
2\sqrt{n} - 2 & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 2\sqrt{n} - 1 \\
{\displaystyle \lim_{n \rightarrow \infty} \frac{2\sqrt{n} - 2}{\sqrt{n}}} & \leq {\displaystyle \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^n \frac{1}{\sqrt{i}}}{\sqrt{n}}} & \leq 1 + {\displaystyle \lim_{n \rightarrow \infty} \frac{2\sqrt{n} - 1}{\sqrt{n}}} \\
2 & \leq {\displaystyle \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^n \frac{1}{\sqrt{i}}}{\sqrt{n}}} & \leq 2 \\
\end{eqnarray*}
That is 
\[ {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} = \Theta(\sqrt{n}).\]


\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%2
\problem (8 points)\\

For each of the following pairs of functions $f(n)$ and $g(n)$, fill
in the blank with $O$, $\Omega$, $\Theta$, $o$ or $\omega$, depending
on whether $f(n)= O(g(n))$, $f(n) = \Omega(g(n))$, $f(n) =
\Theta(g(n))$, $f(n) = o(g(n))$ or $f(n) = \omega(g(n))$. If there is
more than one relation between $f(n)$ and $g(n)$, write only the
strongest one (a relation $X$ is stronger than another relation $Y$ if
$X$ implies $Y$ but the converse does not hold). The first line is an
example solution. Note: $\lg n = \log_2 n$.\\ 
\
\def\blank{\rule[-2pt]{.5in}{.5pt}}
\[
\begin{array}{rcrl}
2n         &=& \stackrel{\textstyle \Theta}{\blank} & (n) \\
&&&\\
\lg (n^3)  &=& \stackrel{\textstyle \Theta}{\blank} & (\lg n)\\
&&&\\
n!         &=& \stackrel{\textstyle \omega}{\blank} & (4^n)\\
&&&\\
2^{\log_3 n} &=& \stackrel{\textstyle o}{\blank} & (n^2)\\
&&&\\
\sum_{i=1}^{n}{1/i} &=& \stackrel{\textstyle \omega}{\blank} & (1)\\
&&&\\
n^{4.01}   &=& \stackrel{\textstyle \omega}{\blank} & (n^4 \lg n)\\
&&&\\
\sum_{i=n}^\infty {1/{i^2}} &=& \stackrel{\textstyle o}{\blank} & (1)\\
&&&\\
{n \choose 10}&=& \stackrel{\textstyle \Theta}{\blank} & (n^{10}) \\
&&&\\
8^{\lg n}  &=& \stackrel{\textstyle \Theta}{\blank} & (n^3)
\end{array}
\]



\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%3
\problem (12 points)\\
Find asymptotic bounds for the following recurrences. You may assume
that $T(n)= \Theta(1)$ for $n \leq 1$ in each part.\\
\bparts

\ppart $T(n)= 2T(n/2)+\Theta(n)$\\

$2(\frac{1}{2})^p = 1 \Rightarrow p = 1$. Hence we have that\\

\begin{displaymath}
T(n) = \Theta(x(1+ \int_{1}^{x} \frac{u\,du}{u^2})) = \Theta(x(1+\ln x)) =
\Theta(x\ln x)
\end{displaymath}
\vspace{0.5in}
\ppart $T(n) = 4T(n/2+ \sqrt n)+ \Theta(n^2)$\\

$4(\frac{1}{2})^p = 1 \Rightarrow p = 2$. Hence we have that\\

\begin{displaymath}
T(n) = \Theta(x^2(1+ \int_{1}^{x} \frac{u^2\,du}{u^3})) = \Theta(x^2(1+\ln x)) =
\Theta(x^2\ln x)
\end{displaymath}
\vspace{0.5in}
\ppart $T(n) = T(\lceil n/3 \rceil)+2T(\floor{n/4})+\Theta(n)$\\

We rewrite the recurrence as $T(n) = T(n/3 + (\lceil n/3 \rceil - n/3))
+ 2T(n/4 + (\floor{n/4} -n/4)) + \Theta(n)$. By taking logs on both
sides of $(\frac{1}{3})^p + 2(\frac{1}{4})^p = 1$ and simplifying, we
get $p = \frac{\ln 2}{\ln 12} < 1$. Hence we have that\\

\begin{displaymath}
T(n) = \Theta(x^p(1+ \int_{1}^{x} \frac{u\,du}{u^{p+1}})) =
\Theta(x^p(1+x^{1-p}) = \Theta(x)
\end{displaymath}
\eparts
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%4
\problem (10 points)\\
Unbeknownst to many, Leonardo Fibonacci had a brother Eduardo who
invented the following sequence of numbers that he called {\em Eduardo}
numbers:

$$e_0 = 1$$
$$e_1 = 3$$
$$ \forall i \geq 2: e_i = e_{i-1} + e_{i-2}$$

Eduardo (who was not so good at math) made 2 conjectures about his numbers:

$$C1: \forall i \geq 0: e_i = f_{i+1} + 2f_i$$
$$C2: \forall i \geq 0: e_i = f_{i+2} - f_i$$

where $f_i$ is the ith Fibonacci number ($f_0 = 0$, $f_1 = 1$, $f_n =
f_{n-1}+f_{n-2}$ for all $n \geq 2$).\\
 
\def\longdash{\rule[.04in]{.1in}{.5pt}}

Decide whether or not Eduardo's conjectures are true.  Prove your
answers.  (Hint: do not repeat Eduardo's mistake by trying to solve
the recurrence exactly $\longdash$ there is a much faster way to
determine if each conjecture is true.)\\

The first conjecture can be proven true by induction as follows:\\

{\em Base cases:} $e_o = 1 = f_1+2f_0, \,\,e_1 = 3 = 1+ 2 = f_2+2f_1$\\

{\em Induction step:} Suppose $e_i = f_{i+1}+2f_i$ for $i<k$, where $k
\geq 2$. We then have that\\
\begin{displaymath}
e_k = e_{k-1}+e_{k-2} = f_k+2f_{k-1} + f_{k-1}+2f_{k-2} = f_{k+1} +
2f_k
\end{displaymath}\\
\vspace{1.5in}
The second conjecture is false. A counterexample is $e_1 = 3 \neq f_3
- f_1 = 1$.

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%5
\problem (10 points)

In the following problem there is no direct connection between the two parts.\\

\bparts 

\ppart Suppose that each pair of a genetically engineered species of
rabbits left on an island produces two new pairs of rabbits at the age
of one month and six new pairs of rabbits at the age of two months and
every month afterwards. None of the rabbits ever die or leave the
island.  Find a recurrence relation for the number of {\em pairs} of
rabbits on the island $n$ months after one newborn pair is left on
the island. Do not solve the recurrence relation.\\
\\
Let $N(t)$ be the number of pairs of rabbits after $t$ months. Then
$N(0)=1$, $N(1)=3$, and we have that, for $t \geq 2$:\\
\begin{displaymath}
N(t) = 7N(t-2) + 3(N(t-1)-N(t-2)) = 3N(t-1) + 4N(t-2)
\end{displaymath}\\
\vspace{0.5in}
\ppart Solve the following inhomogeneous recurrence relation:\\
\begin{displaymath} 
f(n) = 6f(n-1)-9f(n-2) +2^n, n \geq 2
\end {displaymath}

The initial conditions are $f(0) = 5, f(1) = 26$.\\
\\
The characteristic equation $r^2-6r+9$ has a repeated root $\alpha =
3$. Hence the homogeneous solution has the form $f_h(n) = A3^n+Bn3^n$,
for some constants $A$ and $B$. To find a particular solution, we try
$f_p(n) = K2^n$. Plugging into the difference equation gives:\\

\begin{math}
K2^n = 6K2^{n-1} -9K2^{n-2}+2^n \Rightarrow K = \frac{6K}{2} - \frac{9K}{4} +1\\
\Rightarrow 4K= 12K-9K+4 \Rightarrow K = 4\\
\end{math}\\
Hence the complete solution has the form $f(n) = A3^n+Bn3^n +2^{n+2}$.
We now use the initial conditions to solve for $A$ and $B$:\\

\begin{math}
f(0) = 5 = A+4 \Rightarrow A = 1\\
f(10 = 26 = 3 + 3B +8 \Rightarrow B = 5\\
\end{math}\\
Hence the solution is $f(n) = 3^n + 5n3^n + 2^n, n \geq 2$.
\eparts

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%6
\problem (10 points)

\bparts 
\ppart Prove, by direct calculation, that the following
binomial identity is true for all $l,m,n$ such that $0 \leq l \leq m
\leq n$ :

\begin{displaymath}
{n \choose m}{m
  \choose l} = {n \choose l}{n-l \choose m-l}
\end{displaymath}\\
We just expand the binomial coefficients and cancel:\\

\begin{math}
{n \choose m}{n \choose l} = \frac{n!}{m!(n-m)!}\frac{m!}{l!(m-l)!} = \frac{n!}{(n-m)!}\frac{1}{l!(m-l)!}=
\frac{n!}{l!(n-l)!}\frac{(n-l)!}{(m-l)!(n-m)!} = {n \choose l}{n-l \choose m-l}
\end{math}\\
\vspace{0.5in}
\ppart Now prove the same identity combinatorially. Let $A$ be an
$n$-element set.  Explain how the left-hand and right-hand sides of the
identity in part a) may be interpreted as the number of ways of
choosing two subsets $B$ and $C$ of $A$, where $|B|=m$, $|C| =l$, and
$C \subseteq B$.\\
\\

The left hand side corresponds to first choosing $B$, then $C$. The
number of ways of doing this is, using the product rule, ${n \choose
  m}{n \choose l}$. The right hand side corresponds to first choosing
$C$, and then choosing $B-C$. The number of ways of doing this is,
using the product rule, ${n \choose l}{n-l \choose m-l}$. Since both
sides are equivalent to the number of ways of choosing subsets $B$ and $C$ such
that $|B|=m$, $|C| =l$, and $C \subseteq B$, the identity holds.
\eparts

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%7
\problem (30 points)\\

Four distinct children approach you on halloween, requesting candy.
You have ten pieces of candy to distribute among them. In how many
different ways can you distribute the ten pieces if: (You must specify
your answer as an integer, or as a ratio of products of integers, or
as an integer raised to the power of an integer)\\ 

\bparts
\ppart All the pieces are the same (Reese's Peanut-butter
Cups$^{(TM)}$). No other restrictions.\\

$${10+4-1 \choose 10} = {13 \choose 10} = \frac{13!}{3!10!}$$\\
\vspace{0.5in}
\ppart All the pieces are the same, and each child must receive at
least one piece. No other restrictions.\\

$${6+4-1 \choose 6} = {9 \choose 6} = \frac{9!}{3!6!}$$\\
\vspace{0.5in}
\ppart All the ten pieces are different. No other restrictions. \\

$$4^{10}$$

\newpage
\ppart Five pieces are Reese's Peanut-Butter Cups $^{(TM)}$ and the other five are
Nestle's Crunch $^{(TM)}$. No other restrictions.\\

$${5+4-1 \choose 5}^2 = {8 \choose 5}^2 = (\frac{8!}{3!5!})^2$$\\
\vspace{0.5in}
\ppart All the pieces are the same. No child gets more than $4$
pieces. No other restrictions.\\
We use the formula for $10$-combinations of $4$ elements with
repetition with each element occuring fewer than $5$ times, and get:\\

$${13 \choose 3} - {4 \choose 1}{8 \choose 3} + {4 \choose 2}{3
  \choose 3} = 68$$
\eparts

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%8
\problem (10 points)\\
In the following problem, you can leave your answers in closed form, that is,
you do not have to write down the coefficients of the generating
functions explicitly.
\bparts
\ppart Give a generating function for the number of ways to compose a bag of
chocolate donuts, which contains at least $3$ donuts.\\
$$G(x) = \frac{x^3}{1-x}$$\\
\vspace{0.5in}
\ppart Give a generating function for the number of ways to compose a bag of
glazed donuts, which contains at most $4$ donuts.\\
$$G(x) = \frac{1-x^5}{1-x}$$\\
\vspace{0.5in}
\ppart Give a generating function for the number of ways to compose a bag of
coconut donuts, which contains exactly $2$ donuts.\\
$$G(x) = x^2$$
\newpage
\ppart Give a generating function for the number of ways to compose a bag of
plain donuts, where the number of donuts in the bag is a multiple of $4$.\\
$$G(x) = \frac{1}{1-x^4}$$\\
\vspace{0.5in}
\ppart Give a generating function for the number of ways to compose a
bag of donuts where the donuts are of $4$ kinds (chocolate, glazed,
coconut and plain) and all the following conditions hold:\\ 

\begin{itemize}
\item at least $3$ are chocolate donuts.
\item at most $4$ donuts are glazed.
\item there are $2$ coconut donuts.
\item the number of plain donuts is a multiple of $4$.
\end{itemize}
\eparts
\vspace{0.5in}
$$ G(x) = \frac{x^3}{1-x} \frac{1-x^5}{1-x}x^2 \frac{1}{1-x^4} = \frac{x^5(1+x^2+x^3+x^4)}{(1-x)(1-x^4)}$$

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problems}

\end{document}



















