%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Shouldn't we scrap the rest, to clean up??
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\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.}

\endinput

\[ {\displaystyle \sum_{p=1}^{\infty} \sum_{q=p}^{\infty} x^py^q}.\]

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