\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{psfig}
\input{macros-course}

\newcommand{\tinyspace}{\ifshowsolutions\else\vspace{1in}\fi}
\newcommand{\smallspace}{\ifshowsolutions\else\vspace{2in}\fi}
\newcommand{\mediumspace}{\ifshowsolutions\else\vspace{3in}\fi}
\newcommand{\largespace}{\ifshowsolutions\else\vspace{4in}\fi}
\newcommand{\hugespace}{\ifshowsolutions\else\vspace{5in}\fi}
\newcommand{\pagespace}{\ifshowsolutions\else\newpage\fi}
\newcommand{\nextproblem}{\newpage}


\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}

\newcommand{\bij}{\mathbin{\mbox{\rm bij}}}
\newcommand{\inj}{\mathbin{\mbox{\rm inj}}}
\newcommand{\sur}{\mathbin{\mbox{\rm sur}}}
\newcommand{\ran}[1]{\text{range}(#1)}
\newcommand{\Union}{\bigcup}

\newcommand{\eqdef}{\mathbin{\mbox{::=}}}

\newcommand{\ROT}{\mbox{ROT}}
\newcommand{\FBT}{\mbox{FBT}}
\newcommand{\brep}{\mbox{rot-to-fbt}}
\newcommand{\unrep}{\mbox{fbt-to-rot}}
\newcommand{\nil}{\mbox{\texttt{()}}}
\newcommand{\sz}{\mbox{size}}
\newcommand{\cons}{\mbox{cons}}
\newcommand{\sbtr}{\mbox{subtrees}}
\newcommand{\kcomp}[1]{\bar{#1}}

\newcommand{\kth}{\ensuremath{^{\textrm{\tiny th}}}}

\newcommand{\fins}{\mathcal{F}}

\newcommand{\kpfend}{}

\newcommand{\kskip}[1]{}

\newcommand{\pts}[1]{\relax[#1 points]\enskip\ignorespaces}
\newcommand{\onept}{\relax[1 point]\enskip\ignorespaces}

\newcommand{\kignore}[1]{}

\makeatletter
\renewcommand\theenumi{\@alph\c@enumi}
\renewcommand\theenumii{\@roman\c@enumii}

\renewcommand\labelenumi{\theenumi)}
\renewcommand\labelenumii{\theenumii)}

\newcommand{\coverpage}[1]{\ifshowsolutions \else #1 \fi}

\def\ps@myheadings{%
\let\@oddfoot\@empty\let\@evenfoot\@empty
\def\@evenhead{\thepage\hfil\slshape\leftmark}%
\def\@oddhead{\rlap{\slshape\rightmark}\hfil\thepage\hfil \llap{Name:\brule{2in}}}%
\let\@mkboth\@gobbletwo
\let\sectionmark\@gobble
\let\subsectionmark\@gobble
}

\makeatother

\askaboutsolutions

\renewcommand{\solution}[1]{\ifshowsolutions\par\textbf{Solution.} #1\fi}
\newcommand{\ksource}[1]{\ifshowsolutions\par\textsc{Source: #1}\fi}

\begin{document}

\ifshowsolutions
\qsol{2}{April 19 2000}
\else
\exam{ Quiz 2}{April 12 2000}
\fi

%\titlebar

\coverpage{
\textbf{Your Name}:\ \mbox{}\hrulefill\mbox{}\par

\textbf{Circle the name of your Tutorial Instructor}:\\
\begin{center}
\begin{tabular}{c@{\hskip 3em}c@{\hskip 3em}c@{\hskip 3em}c}
Carl & David & Josh & Ken \\
\ &&& \\
Kyle & Robert & Shishir & Victor
\end{tabular}
\end{center}

\medskip

\noindent Write the hour at which your Friday recitation begins \brule{3em}

\medskip

\begin{closeitemize}
\item This quiz is open book/notes.  

\item Put your name on the top of {\bf every} page --- \emph{these
pages may be separated for grading}.

\item Write your solutions in the space provided.  If you need more
space, write on the back of the sheet containing the problem.
Please keep your entire answer to a problem on that problem's page.

\item You may assume any of the results presented in class or in the
  lecture notes, but you must \textit{explicitly} cite which results
  you are using and how you are using them.

\item Show your work, as partial credit will be given.  You will be
graded not only on the correctness of your answer, but also on the
clarity with which you express it.

\item {\bf Be neat and write legibly}.

\item GOOD LUCK!
\end{closeitemize}

\bigskip

\medskip

\hrule
\smallskip
\centerline{\textbf{DO NOT WRITE BELOW THIS LINE}}
\smallskip
\hrule

\medskip

\begin{center}
\renewcommand{\arraystretch}{.3}
\begin{tabular}{|c|c|c|c|}
\hline
& &\hspace*{1in}&\\
Problem & Points & Grade & Grader\\
& & & \\ \hline \hline
& & & \\
1 &  10 & & \\ & & & \\\hline & & &\\
2 &  20 & & \\ & & & \\\hline & & &\\
3 &  10 & & \\ & & & \\\hline & & &\\
4 &  10 & & \\ & & & \\\hline & & &\\
5 &  10 & & \\ & & & \\\hline & & &\\
6 &  10 & & \\ & & & \\\hline & & &\\
7 &  10 & & \\ & & & \\\hline & & &\\
8 &  10 & & \\ & & & \\\hline & & &\\
9 &  10 & & \\ & & &\\
\hline
\hline
& & &\\
Total & 100 & & \\
& & &\\
\hline
\end{tabular}
\end{center}


\newpage
}

\begin{problems}

\problem\pts{10}
\ksource{Pigeonhole principle -- Fall 99 tut 7}
\bparts

\ppart\pts{5}
$n>1$ people attend a party.  Prove that there must be two people who
shake the same number of hands, assuming no one can shake his own
hand.

\mediumspace
\solution{A straightforward application of the pigeonhole principle.
Since no person can shake his own hand, the number of hands he can
shake must be an integer from $0$ to $n-1$.  If no two people shook
the same number of hands, then every one of these $n$ numbers from $0$
to $n-1$ must equal the number of times some person shook hands.  But
that would mean that some person shakes $0$ hands while some other
person shakes $n-1$ hands, i.e., for all the other people.  This is a
contradiction.  }

\ppart\pts{5} Consider a set $S$ of 10 natural numbers chosen from the
range $1,\ldots,50$.  Prove that there must be two distinct subsets of
$S$ that sum to the same value.  

\eparts


\newpage
\problem\pts{20}\textbf{Counting}

For the problems below, you may leave products and binomial
coefficients in your final answer.

\bparts
\ppart\pts{5} In poker, a \emph{flush} is a set of five cards, all of the
same suit.  How many distinct flushes are there?

\smallspace
\ppart\pts{5} In poker, a \emph{straight} is a set of cards that, when
the suits are ignored, form a five-in-a-row sequence, for example
$5,6,7,8,9$ or $8,9,10,J,Q$.  An ace can start a straight
($A,2,3,4,5$) or end it ($10,J,Q,K,A$) but cannot wrap around ({\bf no}
$Q,K,A,2,3$).  How many distinct straights are there?

\smallspace
\ppart\pts{5} A \emph{straight flush} is a hand that is both a
straight and a flush: 5 cards in a row, all the same suit.  How many
are there?

\smallspace
\ppart\pts{5} How many 5-card hands are there containing a straight
\emph{or} a flush?

\eparts


% ps8 : f95 : 3
\newpage
\problem\pts{10} \textbf{Counting}
\ksource{Fall 95 pset 8 n.3}

Consider placing $n$ distinguishable books on $r$
distinguishable shelves.

\bparts 

\ppart\pts{5} If the order of books on each shelf doesn't matter, how many
distinct placements are there?

\mediumspace
\ppart\pts{5} If order on the shelf matters, how many distinct placements
are there?

\solution{For the first book there are $r$ choices. For the next book
there are $r+1$ choices since we can think of the first book as
splitting the shelf it is put on into two shelves. Similarly for the
third book there are $r+2$ choices. In this way we see that the
total number of ways, by the product rule, is $r\times (r+1) \times
(r+2) \ldots (n+r-1) $.}

\eparts



\newpage
\problem\pts{10} \textbf{Order of Growth}
\ksource{New}

\bparts

\newcommand{\kalg}{\ensuremath{\mathbb{A}}}
\ppart\pts{5} From lecture, we know that any comparison-based sorting
algorithm \kalg{} must take time $\Omega(n\log n)$ on $n$ elements.
Which of the following is a consequence of this fact?  Explain your
answer.
%
\begin{enumerate}
\item There is some constant $c>0$ for which all executions of \kalg{}
  will perform exactly $cn\log n$ steps.
\item There is some constant $c>0$ for which all executions of \kalg{}
  will perform at least $cn\log n$ steps.
\item\label{OG:ANS} There is some constant $c>0$ for which the longest
  executions of \kalg{} will perform at least $cn\log n$ steps.
\item There is some constant $c>0$ for which all executions of \kalg{}
  will perform at most $cn\log n$ steps.
\item There is some constant $c>0$ for which the longest executions of
  \kalg{} will perform at most $cn\log n$ steps.
\end{enumerate}

\smallspace
\solution{\ref{OG:ANS} is the correct answer.  $\Omega$-notation
deals only with worst-case lower bounds; $\Omega(n\log n)$ is a lower
bound on the number of steps required for the
\textit{worst-case} input to \kalg{}.
}

% This can obviously be changed to something else.  I just want them
% to be able to apply the definition. - Kyle
\ppart\pts{5} Prove that $10n^2=O(n^3)$.

\solution{$10n^2\leq c\cdot n^3$ for all $n\geq 1$ when $c\geq 10$, so
the theorem follows.}

\eparts





\newpage
\problem\pts{10} \textbf{Summations}
\ksource{New}

\begin{problemparts}

\ppart\pts{5} Express the following in closed form 
\[ {\displaystyle \sum_{p=1}^{\infty} \sum_{q=p}^{\infty} x^py^q}.\]
(Note that the lower indices are not constants.)

\pagespace
\solution{
\begin{eqnarray*}
{\displaystyle \sum_{p=1}^{\infty} \sum_{q=p}^{\infty} x^py^q} & = {\displaystyle \sum_{p=1}^{\infty} x^py^p \sum_{q=p}^{\infty} y^{q-p}} & \\
 & = {\displaystyle \sum_{p=1}^{\infty} x^py^p \sum_{r=0}^{\infty} y^r} & \\
 & = {\displaystyle \left( \sum_{p=1}^{\infty} x^py^p  \right) \left( \sum_{r=0}^{\infty} y^r \right)} & \\
 & = \left( \frac{xy}{1-xy}\right)\left( \frac{1}{1-y}\right).
\end{eqnarray*}
}

\ppart\pts{5} Prove tight asymptotic bounds on 
\[
\sum_{n=1}^m \frac{1}{n\ln n}.
\]
{\bf Hint:} consider $\frac{d}{dx}\ln\ln x$.

\end{problemparts}


% ps7 : f95 : 6
\newpage
\problem\pts{10} \textbf{Binomial Coefficients}
\ksource{Fall 95 pset 7 n.6}

Prove that
\[ {\displaystyle \sum_{k=1}^n}k\left(\begin{array}{c} n\\ k\end{array}\right) = n2^{n-1} \]
\bparts

\ppart\pts{5} using a combinatorial argument.  {\bf Hint:} choose a
committee and a leader.

\mediumspace
\solution{Consider the number of ways of picking a team of size
  $k$ from a group of $n$ people and designating one of them captain.
  This can be done in $k{n\choose k}$ ways, for all $k =
  0,1,\ldots,n$. But the total number of ways of doing this can also
  be counted differently. First select the captain - $n$ ways - then
  select an arbitrary subset of the rest - $2^{n-1}$ ways. Hence the
  result follows.}

\ppart\pts{5} by finding a closed form for $ {\displaystyle
  \sum_{k=1}^n}\left(\begin{array}{c} n\\ k\end{array}\right)kx^k$ and
  evaluating it at $x=1$.

\solution{
Differentiating 
\[(1+x)^n = {\displaystyle \sum_{k=0}^n {n\choose k}x^k}\]
we get
\[n(1+x)^{n-1} = {\displaystyle \sum_{k=1}^n k{n\choose k}x^{k-1}}\]
and evaluating it at $x=1$ we get the desired result.}

\eparts




\kignore{
\newpage
\problem\pts{10} \textbf{Combinatorics}
\ksource{?}

\begin{theorem*} Suppose $0
\leq r\leq m,n$.  Then
  \[
  {m+n \choose r} = \sum_{k=0}^r {m \choose r-k}{n\choose k}
  \]
\end{theorem*}
Give a combinatorial argument proving the theorem.

\solution{Suppose there are $m$ red balls and $n$ blue balls, all
  distinct.  There are ${m+n \choose r}$ ways to choose $r$ balls from
  the two sets combined.  This is the LHS of the identity.  Now
  decompose this collection of choices based on how many of the chosen
  balls are blue and how many are red.  For any $k$, $0 \leq k \leq
  r$, there are ${m \choose r-k}$ ways to choose $r-k$ red balls, and
  ${n \choose k}$ ways to choose $k$ blue balls.  By the product rule,
  that makes ${m \choose r-k} {n\choose k}$ ways to choose $r$ balls
  such that $k$ of them are blue.  Adding up these numbers for all $k$
  we have that this is $\sum_{k=0}^r {m \choose r-k}{n\choose k}$
  which is the RHS.}
}



\newpage
\problem\pts{10} \textbf{Recurrences}
\ksource{CLR, p. 63}

Consider the following recurrence to which the master theorem
\textit{does not apply:}
\[ T(n)=2T(n/2)+n\log_2 n \]


\bparts

\ppart\pts{3} Perform two iterations of plug-and-chug to reveal a
pattern for this recurrence.

\smallspace

\ppart\pts{7} Prove tight asymptotic bounds for this recurrence.  You
may assume $n$ is a power of two if it is convenient.

\hugespace
\solution{The master theorem does not apply (c.f. CLR, p.63). So, we
  expand:
  \begin{eqnarray*}
    T(n) &=& 2T(n/2) + n\log n \\
    &=& 2^2T(n/2^2) + \frac{n}{2}\log\frac{n}{2} + n\log n \\
    &=& 2^3T(n/2^3) + \frac{n}{2^2}\log\frac{n}{2^2} +
    \frac{n}{2}\log\frac{n}{2} + n\log n \\ 
    &\vdots& \\
    &=& 2^{\log n}T(n/2^{\log n}) + \frac{n}{2^{\log
        n-1}}\log\frac{n}{2^{\log n-1}}
    + \cdots + \frac{n}{2^2}\log\frac{n}{2^2} + 
    \frac{n}{2}\log\frac{n}{2} + n\log n \\ 
    &=& \Theta(n) + n\log n\sum_{i=0}^{\log n-1}
    \left(\frac{1}{2}\right)^i - n\sum_{i=0}^{\log n-1}
    i\left(\frac{1}{2}\right)^i \\
    &=& \Theta(n) + n\log n\left(\frac{1-1/n}{1/2}\right)
    - n\left(\frac{1/2-(1/n)\log n+(\log n-1)(1/2n)}{1/4}\right) \\
    &=& \Theta(n\log n)
  \end{eqnarray*}
}
\eparts





\newpage
\problem\pts{10} \textbf{Recurrences}
\ksource{New}

The Millicent computer virus has been spreading on computers around
MIT.  Once a copy of Millicent enters a computer, it is copied to two
new (uninfected) computers after one day, then to 3 new computers the
second day, and then detected and removed on the third day.
Millicent's creator installed Millicent on 2 computers on day 0 and 2
additional computers on day 1.

\begin{problemparts}


\ppart\pts{3} Due to a tip from inside the FBI that Millicent might be
of extraterrestrial origin, Frohike and Langley have been
investigating the growth of the Millicent virus; however, they've
gotten stuck.  Help them by stating a recurrence describing the number
of computers newly infected on day $n$ for $n>1$.

\tinyspace
\solution{$T_n=2T_{n-1}+3T_{n-2}$}

\ppart\pts{4} Find a closed form for the recurrence you
stated in the previous part.

\pagespace
\ppart\pts{3} Fearing the efforts of the mighty Frohike and suave
Langley, Millicent's creator became frightened and decided to start
installing the virus on 5 new computers every day after day 1.  State
a recurrence for the revised problem and find a closed form solution
for the number of computers newly infected on day $n$.

\solution{First, find the general solution to the homogeneous
recurrence.  The characteristic equation is $x^2-2x-3=0$, which has
roots at 3 and $-1$.  The general solution is then of the form
\[T_n=A3^n+B(-1)^n \]  Now we need to find a particular solution to
the inhomogeneous recurrence.  Since the inhomogeneous term is
constant, we guess a constant solution $b$: \[b = 2b + 3b + 5
\Longrightarrow b = -\frac{5}{4}\] Therefore, the inhomogeneous
recurrence has the simple particular solution $T_n=-5/4$.  We now need
to determine the constants on the complete solution
\[T_n=A3^n+B(-1)^n-\frac{5}{4}\] by plugging in the initial
conditions and solving the resulting system:
\begin{eqnarray*}
T_0 = 2 &=& A + B - \frac{5}{4} \\
T_1 = 2 &=& 3A - B - \frac{5}{4}
\end{eqnarray*}
which has the solution $A=B=13/8$.  The closed form for this
recurrence is then \[T_n = \frac{13}{8}3^n + \frac{13}{8}(-1)^n -
\frac{5}{4}\]  We can perform a sanity check to make us more confident
of our answer:
\begin{center}
\begin{tabular}{l}
$T_2=2\cdot 2 + 3\cdot 2 + 5 = 15$ \\
$T_2=(13/8)3^2 + (13/8)(-1)^2 - 5/4 = 15$ \\ \hline
$T_3=2\cdot 15 + 3\cdot 2 + 5 = 41$ \\
$T_3=(13/8)3^3 + (13/8)(-1)^3 - 5/4 = 41$
\end{tabular}
\end{center}

}

\end{problemparts}




\newpage
\problem\pts{10} \textbf{Countability}
\ksource{New}

\begin{problemparts}

\ppart\pts{5} A function $f$ from the natural numbers to the natural numbers
is \emph{strictly increasing} if $f(n+1)>f(n)$ for every $n$.  Prove that 
the set of such strictly increasing functions is uncountable.

\mediumspace

\ppart\pts{5} A function $f$ from the natural numbers to the natural
numbers is \emph{strictly decreasing} if $f(n+1)<f(n)$ for every $n$.
Prove that the set of such strictly decreasing functions is
uncountable.  {\bf Hint:} first figure out how to prove that the set
of strictly decreasing functions for which $f(0)=1$ is countable.
\end{problemparts}


\end{problems}

\end{document}


\bparts \ppart\pts{5} Ben Bitdiddle hears in class that the power set
of the natural numbers is uncountable.  He sweats over a hot X
terminal for several hours, and then claims to have constructed a
bijection from the power set of the natural numbers to the set of real
numbers, showing that the reals are uncountable.

Given a subset $S\subseteq\naturals$, a binary expansion of the
corresponding real number is the bitstring in which the $n\kth$ digit
is 1 if and only if $n\in S$.  Denote the mapping from
$2^\naturals\rightarrow \reals$ by $f$.  So, for example,
$f(\set{1,3,4})=.1011$ and
$f(\set{2,4,6,8,10,\ldots})=.01010101\ldots$.

Ben claims $f$ is a bijection.  ``$f$ is injective,'' he says, ``since
$f(S)=f(T)$ implies that the corresponding digits in the two real
numbers have ones in exactly the same positions, so $S$ and $T$ must
contain exactly the naturals corresponding to the indices of those
positions.''  He goes on to say that $f$ is surjective, since every
possible real number $r$ can be represented as a (possibly
infinitely-long) binary string, so clearly we can construct a set $S$
such that $f(S)=r$.

While the real numbers are indeed uncountable, something is wrong with
Ben's proof.  Explain the problem.

\mediumspace
\solution{Ben claims $f$ is injective while it is not.  Remember that
$.1=.01111\ldots$, so in fact $f(\set{1})=f(\set{2,3,4,\ldots})$ while
obviously $\set{1}\not=\set{2,3,4,\ldots}$.}

\eparts

Find a closed form for
\[
\sum_{i=0}^n \left[zx^i
\left(1+\sqrt{\left[\sum_{k=0}^m y^k\right]^i} \right)
\left(1-\sqrt{\left[\sum_{\ell=0}^m y^\ell\right]^i} \right)\right]
\]
and specify the regions in which your closed form is not defined.

\solution{Denote $\beta=\sum_{k=0}^m y^k=\sum_{\ell=0}^m
y^\ell=(y^{m+1}-1)/(y-1)$.  Then,
\begin{eqnarray*}
\sum_{i=0}^n \left[zx^i
\left(1+\sqrt{\beta^i} \right)
\left(1-\sqrt{\beta^i} \right)\right]
&=&\sum_{i=0}^n \left[zx^i
\left(1-\beta^i \right)\right] \\
&=&z\left(\sum_{i=0}^n x^i -
\sum_{i=0}^n \left[x\beta\right]^i\right) \\
&=&z\left(\frac{x^{n+1}-1}{x-1} - \frac{(x\beta)^{n+1}-1}{x\beta-1}\right)
\\
\end{eqnarray*}
where $x\not=1$, $y\not=1$, and $x\beta\not=1$.
}


% This has the same story as the previous problem, except that the
% inhomogeneous part is nonlinear.  This may be too hard for them.
\newpage
\problem\pts{10} \textbf{Recurrences}
\ksource{New}

Frohike and Langley have been computing the population growth rate of
a certain type of EBE (extraterrestrial biological entity) under
controlled conditions.  They have determined that these EBE's have two
offspring in their first year, three offspring in their second year,
and then die.  In addition, $4n+4$ EBE's spontaneously appear in each
year $n\geq 2$ through invasions of other hosts.

\bparts 
\ppart\pts{3} State the recurrence describing the total number of new
EBE's in year $n$ for $n>1$. 

\smallspace
\solution{$T_n=2T_{n-1}+3T_{n-2}+4n+4$}

\ppart\pts{7} In their experiment, there were 2 new EBE's in year 0
and 2 new EBE's in year 1.  Find a closed form for the recurrence you
stated in the previous part.

\solution{First, find the general solution to the homogeneous
recurrence.  The characteristic equation is $x^2-2x-3=0$, which has
roots at 3 and $-1$.  The general solution is then of the form
\[T_n=A3^n+B(-1)^n \]  Now we need to find a particular solution to
the inhomogeneous recurrence.  Since the inhomogeneous term is linear,
we guess a linear solution $an+b$:
%
\begin{eqnarray*}
&& an+b = 2[a(n-1)+b] + 3[a(n-2)+b] + 4n+4 \\ 
& \Longrightarrow & a = 2a+3a+4 \Rightarrow a=-1 \\
& & b = -2a + 2b -6a + 3b + 4 \Rightarrow b=-3
\end{eqnarray*}
%
Therefore, the inhomogeneous recurrence has the simple particular
solution $T_n=-n-3$.  We now need to determine the constants on
the complete solution
\[T_n=A3^n+B(-1)^n-n - 3\] by plugging in the initial
conditions and solving the resulting system:
\begin{eqnarray*}
T_0 = 2 &=& A + B - 3 \\
T_1 = 2 &=& 3A - B - 1 - 3
\end{eqnarray*}
which has the solution $A=11/4$ and $B=9/4$.  The closed form for this
recurrence is then \[T_n = \frac{11}{4}3^n + \frac{9}{4}(-1)^n - n -
3\] We can perform a sanity check to make us more confident of our
answer:
\begin{center}
\begin{tabular}{l}
$T_2=2\cdot 2 + 3\cdot 2 + 8 + 4 = 22$ \\
$T_2=(11/4)3^2 + (9/4)(-1)^2 - 2 - 3 = 22$ \\ \hline
$T_3=2\cdot 22 + 3\cdot 2 + 12 + 4 = 66$ \\
$T_3=(11/4)3^3 + (9/4)(-1)^3 - 3 - 3 = 66$
\end{tabular}
\end{center}

}

\eparts


\newpage
\problem\pts{10} \textbf{Recurrences}
\ksource{New}

Find a closed form for the recurrence \[ T_n=T_{n-1}+6T_{n-2} \] given
the initial conditions $T_0=5$ and $T_1=1$.

\solution{
The characteristic equation for this recurrence is $x^2-x-6=0$, which
has roots at $3$ and $-2$.  So, the general form for the solution is
\[ T_n = A3^n+B(-2)^n \] for which we have to determine the constants
$A$ and $B$.  

Plug in the initial conditions to get a system of two equations with
two unknowns:
\begin{eqnarray*}
5 &=& A + B \\
1 &=& 3A - 2B
\end{eqnarray*}
Thus, $A=11/5$ and $B=14/5$, so the solution to the recurrence is
\[\frac{11}{5}3^n + \frac{14}{5}(-2)^n\]  We can perform a sanity
check to make us more confident of our answer:
\begin{center}
\begin{tabular}{l}
$T_2=1 + 6\cdot 5 = 31$ \\
$T_2=(11/5)3^2 + (14/5)(-2)^2 = 99/5 + 56/5 = 155/5 = 31$ \\ \hline
$T_3=31 + 6\cdot 1 = 37$ \\
$T_3=(11/5)3^3 + (14/5)(-2)^3 = 297/5 - 112/5 = 185/5 = 37$
\end{tabular}
\end{center}
}



\newpage
\problem\pts{10}
\ksource{Pigeonhole principle -- Fall 98 rec 7}
Suppose $n > 1$ and we place checkers on exactly $n+1$ squares of
the $n \times n$ checkerboard.  Show that some length occurs more than
once as the distance between two different checkered squares.  (More
precisely, there are checkered squares $S1\neq S2$ and $S3\neq S4$ such
that the distance between $S1$ and $S2$ is the same as the distance
between $S3$ and $S4$, but $\set{S1,S2} \neq \set{S3,S4}$.)

\solution{
The distance between checkers at distinct positions $(x_1,y_1)$ and
$(x_2,y_2)$ is uniquely determined by the set of two numbers
$\set{\abs{x_1 - x_2}, \abs{y_1 - y_2}}$.  The values of these differences
can be $0,\dots,n-1$ except that both can't be zero since the positions
are different.  These are the holes.  So there are $n(n+1)/2 - 1$ holes.

Each set of two checkers is a pigeon.  There are $(n+1)n/2$ pigeons by
reasoning as in (a).  A pigeon gets assigned to a hole which is the
difference of the $x$ and $y$ coordinates of the checker positions.  Since
there is one more pigeon than hole, there must be two pigeons in the same
hole.  That means the $x$ and $y$ coordinate differences, and hence the
distance, between the two pigeons is the same.
}


\newpage
\problem\pts{10} \textbf{Combinatorics}
\ksource{Fall 99 rec 18}

\begin{theorem*} For any $k$
and $n$ such that $n \geq k \geq 0$,
\[
\sum_{m=k}^n  \binom{m}{k} = \binom{n+1}{k+1}.
\]
\end {theorem*}
Give a combinatorial argument proving the theorem.

\textbf{Hint:} Classify subsets of $k+1$ elements from $\set{1,\dots,
n+1}$ by their maximum element.

\solution{

Combinatorial argument:

\begin{proof}

We know the righthand side of the equation is the number of ways to
choose $k+1$ elements from $\set{1,\dots, n+1}$.

For any such subset, the maximum element $m+1$ must satisfy $k+1 \leq
m+ 1\leq n+1$.  For each $m \in \set{k,\dots,n}$, there are
$\binom{m}{k}$ subsets of $k+1$ elements from $\set{1,\dots, m+1}$
whose maximum element is $m+1$.  So the lefthand side of the equation
also counts the number of such subsets.

\end{proof}
For the record, here's an algebraic proof:

\begin {proof}
We prove the theorem by induction on $n$.

{\em Base Case:} $n=0$. Then also $k=0$ and the statement
of the theorem simplifies to
\[ \binom{0}{0} = \binom{1}{1} \]
which is true.

{\em Inductive Step:}  We distinguish two cases.
If $n=k$ then the statement of the theorem simplifies to
\[ \binom{n}{n} = \binom{n+1}{n+1} \]
which is true. Otherwise, we proceed as follows:

\[ \begin {array}{rcll}
\binom{n+1}{k+1} & = & \binom{n}{k} + \binom{n}{k+1} & \mbox{By
Pascal's equality}\\
& = & \binom{n}{k} +  \sum_{m=k}^{n-1}  \binom{m}{k} & 
\mbox{By Inductive Hypothesis}\\
& = & \sum_{m=k}^{n}  \binom{m}{k} &  \mbox{QED}
\end {array} \]
\end {proof}

}


\newpage
\problem\pts{10} \textbf{Order of Growth}
\ksource{New, but hardly original}

Prove that the following recurrence is $O(n)$:
\[ T(n)=T(n/2)+T(n/8)+n \]
(Assume $T(n)=\Theta(1)$ for $n\leq 1$.)

\solution{We prove that $\exists c$ such that $T(n)\leq cn$:
\begin{eqnarray*}
T(n) &=& T(n/2)+T(n/8) + n \\
& \leq & c(n/2) + c(n/8) + n \\
& = & (c/2 + c/8)n + n\\
& = & (5c/8+1)n
\end{eqnarray*}
which is less than $cn$ when $c\geq 8/3$.
}


% Bionomial coefficients
% ps7 : f94 : 2
\newpage
\problem\pts{10} \textbf{Counting}
\ksource{Fall 94 pset 7 n.2}

In how many ways can a rook go from the lower-left corner of an
$m$-by-$n$ chess board to the upper-right corner by a shortest path,
that is, a path that consists of $m+n-1$ squares?

\solution{The rook must make $m-1$ moves up and $n-1$ moves right,
  but the order is arbitrary.  A path is defined by which of the
  $n+m-2$ total moves are the ``up'' moves.  Thus we may choose
  different paths simply by choosing which of the moves should be the
  ``up''s, so there are ${m+n-2 \choose m-1} = {m+n-2 \choose n-1}$
  possible paths.}


% ps3 : f99 : 2b
\newpage
\problem\pts{10} \textbf{Counting}
\ksource{Fall 99 pset 3 n.2b}
 
How many distinct truth tables for propositions involving $n$
variables are there---that is, how many functions are there that take
$n$ boolean variables as input and produce a single boolean value as
output?

\solution{There are $2^n$ lines (assignments) in the truth table for a
formula with $n$ variables, since each of the variables can take
on one of two values.  For a given truth assignment to the $n$
variables, the proposition can be either true or false; hence,
there are $2^{2^n}$ possibilities.}


% Incl/excl
% ps7 : f94 : 9
\newpage
\problem\pts{10}
\ksource{Inclusion-Exclusion -- Fall 94 pset 7 n.9}

How many integers in the range from 1 to 2414 are not divisible by any
of the numbers 18, 23, and 36?  You can leave your answer in terms of
binomial coefficients.

\solution{First, if a number is divisible by 36, then it is also
divisible by 18, so we can simplify our problem.  Now, we use
inclusion-exclusion to count the number of integers from 1 to 2414 not
divisible by 18 or 23.  Make a table, and add the numbers with
appropriate signs:

\begin{tabular}{|c|r|r|c|}
\hline
divisible by & least common multiple & number of integers & include/exclude \\
each of      & of divisors           &from 1 to 2414     & $+/-$\\
\hline
\hline
&   1 & 2414 & $+$ \\
18        &  18 & 134 & $-$ \\
23        &  23 & 104 & $-$ \\
18, 23    &  414 & 5 & $+$ \\
\hline
\end{tabular}

\hspace{3in} These add up to 2181.}

