\documentclass[11pt, twoside]{article}

\usepackage{multirow}

\usepackage{graphics}
\usepackage{psfig}

\input{macros-course}

%\newcommand{\nand}{|}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Printing the page layout parameters

\printlayout

\askaboutsolutions

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

\ifshowsolutions
  \newcommand{\reading}[1]{}
%
  \newcommand{\handoutlabel}{sol6}
  \newcommand{\handouttitle}{Problem Set 6 Solutions}
  \newcommand{\handoutdate}{March 30, 2000}
  \newcommand{\collaboration}{}
  \newcommand{\titlebar}{\handout{\handoutlabel}{\handouttitle}{\handoutdate}}
%
\else 
  \newcommand{\reading}[1]{%
%    \mbox{}\\ %
    \hrule\mbox{} \\ %\bigskip %
    #1%
%    \mbox{} \\ %\bigskip %
    \hrule %
    %\vfill\mbox{}\newpage%
    }
%
  \newcommand{\handoutlabel}{ps6}
  \newcommand{\handouttitle}{Problem Set 6}
  \newcommand{\handoutdate}{March 14, 2000}
  \newcommand{\duedate}{March 28, 2000}
  \newcommand{\collaboration}{\collaborationnote}
  \newcommand{\titlebar}{%
    \handout{\handoutlabel}{\handouttitle}{\handoutdate}
    \centerline{{\bf Due  Date: \duedate.}}
    \vspace*{\baselineskip}}
%
\fi

\renewcommand{\solution}[1]{%
  \ifshowsolutions %
  \textbf{Solution.} \par %
  #1
  \mbox{} \\
  \mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
  \raisebox{-0.25\baselineskip}{$\square$}%
  \hspace*{1ex}\ignorespaces\hrulefill%
  \nopagebreak%
  \fi}


%\newcommand{\solutionname}{Solution}
%\renewenvironment{solution}[1][\solutionname]{%
%  \par
%  \normalfont
%  \topsep6\p@\@plus6\p@ \trivlist
%  \item[\hskip\labelsep\bfseries
%    #1\@addpunct{.}]~~\ignorespaces
%}{%
%\mbox{} \\
%\mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
%\raisebox{-0.25\baselineskip}{$\square$}%
%\hspace*{1ex}\ignorespaces\hrulefill%
%\nopagebreak%
%}

%\renewcommand{\solution}[1]{%
%  %\begin{solution}
%    #1
%  %\end{solution}
%  }

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

\begin{document}

\titlebar

\reading{%
  \vspace{-2\baselineskip}
  \begin{description}\itemsep 0\baselineskip
  \item[Self-study:] \mbox{} \\
    Rosen, Section 1.8, on the growth of functions. \\
    Self-study problems: 3,7,9,11,13,15,17,19,23,31
    
  \item[Reading:] \mbox{} \\[-\baselineskip]
    \vspace*{-0.5\baselineskip}
    \begin{description}\itemsep 0\baselineskip
    \item[Rosen:] Sections 5.1, 5.2, 5.3, 4.1, 4.2
    \item[6.042 Fall 97 Lecture notes (available from course webpage):] %
      Lectures 9--12
    \end{description}
  \end{description}
  }

\section*{Problems:}

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem %
Determine the flaw in the following reasoning and explain your answer.

\[
\left( \sum_{j=1}^n a_j \right) \left( \sum_{k=1}^n 1/a_k \right) =
\sum_{j=1}^n \sum_{k=1}^n a_j/a_k =
\sum_{k=1}^n \sum_{k=1}^n a_k/a_k =
\sum_{k=1}^n \sum_{k=1}^n 1 =
\sum_{k=1}^n n = n^2
\]

\solution{%
  Here, the problem is taking the second step.  It is incorrect to
  change the variable of the first summation to $k$ since the second
  summation uses that variable.  By doing this change of variables, we
  change the meaning of the double summation.
  %
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
% problem 2, problem set 6, fall 1996

Find a closed-form expression for the summation
$\displaystyle\sum_{i=1}^n{i^2x^i}$.% and prove your answer is correct.

\solution{%
  %\begin{solution}
  In the lecture and the lecture notes we derived the following:
    
    \[{\displaystyle \sum_{i=1}^n ix^i} = \frac{x - (n+1)x^{n+1} + nx^{n+2}}{(1-x)^2}.\] 

    Differentiating (with respect to $x$) the above expression and
    multiplying with $x$ we find that

    \[{\displaystyle \sum_{i=1}^n i^2x^i} = \frac{x+x^2-(n+1)^2x^{n+1}+(2n^2+2n-1)x^{n+2}-n^2x^{n+3}}{(1-x)^3}\]

    \remove{%
      We prove that the above closed-form expression for the summation
      is correct by induction on the upper bound $n$ of the summation.
      In particular, let $P(n)$ be the predicate that:

    \[{\displaystyle \sum_{i=1}^n i^2x^i} = \frac{x+x^2-(n+1)^2x^{n+1}+(2n^2+2n-1)x^{n+2}-n^2x^{n+3}}{(1-x)^3}.\]

    Base Case. $P(1)$ is true since

    \[{\displaystyle \sum_{i=1}^1 i^2x^i} = x = \frac{x+x^2-4x^2+3x^3-x^4}{(1-x)^3}.\]

    Inductive Step. Assume $P(n)$ is true. Then
    \begin{eqnarray*}
      {\displaystyle \sum_{i=1}^n i^2x^i} + (n+1)^2x^{n+1} & = & \\
      {\displaystyle \sum_{i=1}^{n+1} i^2x^i} & = & \frac{x+x^2-(n+1)^2x^{n+1}+(2n^2+2n-1)x^{n+2}-n^2x^{n+3}}{(1-x)^3} + (n+1)^2x^{n+1} \\
      & = & \frac{x+x^2-(n+2)^2x^{n+2}+(2(n+1)^2+2(n+1)-1)x^{n+3}-(n+1)^2x^{n+4}}{(1-x)^3}
    \end{eqnarray*}

    Thus $P(n+1)$ is true. Hence, $P(n)$ is true for all $n$.
    %
    }
  %\end{solution}
  }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\clearpage
\problem
% problem 3, problem set 6, fall 1996
% similar to CLR 3.2-1

Show that $\sum_{k=1}^{\infty}{1/k^{3/2}}$ is bounded from above by a
constant.

\solution{%
  %\begin{solution}
    We use the integral method for bounding the infinite sum. Since
    $f(k)=\frac{1}{k^{3/2}}$ is monotonically decreasing for $k>1$, we
    have:
    \begin{eqnarray*}
      \sum_{k=1}^\infty{1/{k^{3/2}}} &=& 1 + \sum_{k=2}^\infty{1/{k^{3/2}}} \\
      &\leq& 1+ \int_1^\infty{\frac{1}{x^{3/2}}}dx\\
      &=& 1 + \left [{\frac{-2}{\sqrt{x}}}\right ]_1^\infty\\
      &=& 1 + (0 + 2)\\
      &=& 3
    \end{eqnarray*}
    Hence, $\sum_{k=1}^\infty{1/{k^{3/2}}} \leq 3$.
  %\end{solution}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

In this problem, we will prove that the ``average'' number of divisors
of a number of size about $n$ is ``about'' $\ln n$.  More formally,
let $t(n)$ be the number of divisors of the number $n$, and let
\[
T(n) = \frac{1}{n} \sum_{j=1}^n t(j)
\]
be the average number of divisors of all numbers less than or equal to
$n$.  Show that $T(n) \sim \ln n$.  

{\bf Hint:} Let the function $f(i,j)=1$ if $i$ is a divisor of $j$,
and $0$ otherwise.  What do the row and column sums of $f(i,j)$ mean?

\solution{%
  Consider the image of the function $f(i,j)$ as a matrix whose rows
  and columns correspond to values of $i$ and $j$ respectively; that
  is, element $(i,j)$ of the matrix denotes whether or not $i$ divides
  $j$.

  \begin{tabular}{cc|ccccccc}
    & & \multicolumn{5}{c}{$j$} \\
    \multirow{5}{1ex}{$i$} & $f(i,j)$ 
    & 1 & 2 & 3 & 4 & 5 & 6 & \multirow{6}{2ex}{$\cdots$} \\
    \hline
    & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
    & 2 & 0 & 1 & 0 & 1 & 0 & 1 \\
    & 3 & 0 & 0 & 1 & 0 & 0 & 1 \\
    & 4 & 0 & 0 & 0 & 1 & 0 & 0 \\
    & $\vdots$  & \multicolumn{6}{c}{$\vdots$}  \\
  \end{tabular}
  
  Notice that the sum of each column $j$ corresponds to the number of
  divisors of the number $j$ and the sum of each row $i$ corresponds
  to the number of multiples of the number $i$.  In fact, the sum of
  the first $n$ elements of a row $i$ correspond to the number of
  multiples of $i$ up to the number $n$, which can be compactly
  represented as $\floor{\frac{n}{i}}$.
  
  It follows that:

  \begin{eqnarray*}
    T(n) & = & \frac{1}{n} \sum_{j = 1}^{n} t(j) \\
         & = & \frac{1}{n} \sum_{i = 1}^{n} \sum_{j = 1}^{n} f(i,j) \\
         & = & \frac{1}{n} \sum_{i = 1}^{n} \floor{\frac{n}{i}}
  \end{eqnarray*}

  $T(n)$ can then be bounded from below and above as follows:

  \begin{eqnarray*}
    \frac{1}{n} \sum_{i = 1}^{n} \paren{\frac{n}{i} - 1}
    & \leq T(n) \leq 
    & \frac{1}{n} \sum_{i = 1}^{n} \frac{n}{i} \\
    \frac{1}{n} \paren{ \sum_{i = 1}^{n} \frac{n}{i} - \sum_{i = 1}^{n} 1} 
    & \leq T(n) \leq 
    & \sum_{i = 1}^{n} \frac{1}{i} \\
    \sum_{i = 1}^{n} \frac{1}{i} - 1 
    & \leq T(n) \leq 
    & \sum_{i = 1}^{n} \frac{1}{i} \\
  \end{eqnarray*}

  In class, we determined that $H_n = \sum_{i = 1}^{n} \frac{1}{i}
  \sim \ln n$.  Thus, it follows that $T(n) \sim \ln n$.
  %
  }

\problem \textbf{Asymptotic notation}
% problem 1, problem set 7, fall 1999

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.

\vspace*{-0.5\baselineskip}

\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} &&&\\\hline
    2^n & 2^{n/2} &&&\\\hline
    \log(n!) & \log(n^n) &&&\\\hline
  \end{array}
\end{equation*}

\solution{
  \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} & \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:\\
  (a) Refer to the lecture notes on $O$-notation. \\
  (b) Polynomial growth versus exponential growth. (See Theorem 3.6,
  Lecture 9, Fall'97.)\\
  (c) When $n$ is a multiple of $\pi$, $n^{\sin n}=1$, so no
  constant times 1 will bound $\sqrt n$ as $n$ ranges over
  multiples of $\pi$. When $n$ is of the form $2k'\pi + \pi/2$,
  for some integer $k'$, then $n^{\sin n}=n$ and $\frac{n}{\sqrt n} =
  \sqrt n$ grows without bound as $k'$ increases.\\
  (d) $\frac{2^n}{2^{n/2}}=2^{n/2}$ grows without bound as $n$
  grows --- it is not bounded by a constant.\\
  (e) See Rosen \S 1.8 Ex. 61, 62.\\
  }

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

\problem \textbf{Recurrences}
% problem 4, problem set 6, spring 1999

Consider a set of record items, each carrying some data and a key and
the following definition of a \emph{majority key}.

\begin{definition*}
  The {\em majority key} of a set of $m$ records is a key that occurs
  more than $m/2$ times.
\end{definition*}

For example, $2$ is the majority key in a set of 3 records which are
tagged, consecutively, by keys $1$, $2$, and $2$.  On the other hand,
in the set of 4 records tagged by keys $1$, $2$, $3$, and $3$, there
is no majority key.

Consider the following algorithm for finding the majority key of a set
of records: If there is an even number of records, we pair adjacent
items up (first with second, third with fourth, etc.) and compare
their keys.  If they have the same key, we keep one of them, otherwise
we throw them both away.  We run this algorithm recursively on the
resulting set.  If there is an odd number of items in our set, we find
the majority key of the set containing all but the last item.  If
there was no majority key then we check if the key of the last record
is the majority key by explicitly counting how many times this key
appears in the whole set.  We continue in this fashion until we either
get one record, in which case we check if its key is in fact the
majority key --- again by counting how many times this key appears in
the original set --- or we end up with no items, in which case we
conclude that there was no majority key.

\begin{problemparts}

\vspace{-\baselineskip}
\problempart %
Prove that if there is a majority key in the initial set of records
then this algorithm terminates with a record item carrying that key.
(Hint: Find an invariant that is preserved at every stage.  Consider
the even and odd cases separately.)

\solution{%
%\begin{solution}
  We model the majority key algorithm as a state machine.  The state
  of the state machine is defined as the tuple $(a, b, s, r)$, where
  $a$ corresponds to the initial list of records, $b$ corresponds to
  the current list of records in which we are still looking for a
  majority key, $s$ corresponds to a list of the odd records that we
  still need to test, and $r$ corresponds to a list containing the
  majority key of the initial list of records $a$.  The initial state
  of the state machine is the state $(a, a, \emptyset, \emptyset)$.
  The set of transitions $(a, b, s, r) \rightarrow (a', b', s', r')$
  is described by the following pseudocode:

  \clearpage
  \begin{tabbing}
    X \= X \= X \= X \= X \= X \= X \= X \kill %
    $\delta: (a, b, s, r) \rightarrow (a', b', s', r')$ \+\\
    \textbf{Precondition:} \+\\
    $(b \not = \emptyset \Or s \not = \emptyset) \And r = \emptyset)$ \-\\
    \textbf{Effect:} \+\\
    $a' = a$ \\
    \textbf{if} $|b| > 1$ \textbf{then} \+\\
    \textbf{if} $|b|$ is even \textbf{then} \+\\
    $b' = \ms{pair-and-remove}(b)$ \\
    $s' = s$ \\
    $r' = r$ \-\\
    \textbf{else} \+\\
    $b' = \ms{pair-and-remove}(b - \ms{last}(b))$ \\
    $s' = \ms{append}(s,\ms{last}(b))$ \\
    $r' = r$ \-\-\\
    \textbf{else} \+\\
    \textbf{if} $|b| = 1$ \textbf{then} \+\\
    \textbf{if} $\ms{is-majority}(a, \ms{last}(b))$ \textbf{then} \+\\
    $b' = \emptyset$ \\
    $s' = \emptyset$ \\
    $r' = \set{\ms{last}(b)}$ \-\\
    \textbf{else} \+\\
    $b' = \emptyset$ \\
    $s' = s$ \\
    $r' = r$ \-\-\\
    \textbf{else} \+\\
    $b' = b$ \\
    \textbf{if} $\ms{is-majority}(a, \ms{last}(s))$ \textbf{then} \+\\
    $s' = \emptyset$ \\
    $r' = \set{\ms{last}(s)}$ \-\\
    \textbf{else} \+\\
    $s' = \ms{remove-last}(s)$ \\
    $r' = r$
  \end{tabbing}

  The state machine thus terminates either when the majority key is
  stored in the list $r$, or when the current list of records $b$ is
  empty and there are no more records in $s$ to test.  If upon
  termination $r$ is empty, then the algorithm has determined that
  there is no majority key.

  Let the predicate $P$ on the states of the state machine be defined
  as follows: if $x$ is a majority key of the initial list of records
  $a$, then $x$ is either the majority element in $b$ or is in $s
  \union r$.  According to the invariant theorem, to prove that the
  property $P$ is invariant, we must show that the property is true in
  all initial states and that it is preserved by any state transition.

  For the base case, the property $P$ is trivially true since $b = a$
  and $s \union r = \emptyset$.  Now, we show that the statement is
  preserved by any transition $(a, b, s, r) \rightarrow (a', b', s',
  r')$ of the state machine.  Note that the predicate is vacuously
  true if the initial list $a$ does not contain a majority key.
  Letting $x$ denote the majority key of $a$, we analyze the various
  cases:

  \begin{description}
  \item[Case 1:] $x$ is the majority element in the list $b$. \\ %
    We we analyze the post-state of the transition by considering the
    cases in which $b$ has one or more elements.  If $b$ has one
    element and that element is $x$, then $r'$ will be a singleton
    list containing $x$, \ie $x \in s' \union r'$.  If $b$ has more
    than one elements, it suffices to show that if $b$ has an even
    number of elements, $x$ is the majority element of $b'$, and
    otherwise, either $x$ is the last element of $b$ and is an element
    of $s'$, or $x$ is not the last element of $b$ and is the majority
    element of $b'$.

    Let $b$ contain an even number of $2 k$ records and $i$ be the
    count of $x$ in $b$, \ie $i \geq k + 1$.  Let $l$ and $d$ denote
    the number of pairs that have same and different elements
    respectively; that is, $2 k = 2 l + 2 d$.  Moreover, let $l'$ and
    $d'$ denote the number of pairs of same and different elements,
    respectively, that contain $x$; that is, $i = 2 l' + d' $.  In the
    post-state of the transition, the number of records is $2k - l - 2
    d$ and the count of the majority element $x$ is $i - l' - d'$.
    Substituting in for $k$ and $i$, we get that the number of records
    and the count of $x$ in $b'$ is $l$ and $l'$, respectively.  In
    order to show that $x$ is the majority element of $b'$, it
    suffices to show that $2 l' \geq l + 1$.  Consider the inequality
    $i \geq k + 1$ and plug in $i = 2 l' + d'$ and $2 k = 2 l + 2 d$.
    It follows that $2 l' + d' \geq l + d + 1$.  But since $d \geq
    d'$, it follows that $2 l' + d' \geq l + d + 1 \geq l + d' + 1$.
    Thus, it is the case that $2 l' \geq l + 1$.  Thus, the element
    $x$ is the majority element of $b'$.

    Let $b$ be a list of an odd number of $2k+1$ records.  If the last
    key is not $x$, then $x$ occurs at least $k+1$ times in the first
    $2k$ records, \ie $x$ is a majority key of the first $2k$ elements
    in $b$ and the prior analysis applies; that is, $x$ is the
    majority element of $b'$.  If $x$ is the last element of $b$, then
    it is appended to the list $s$; that is, $x$ is an element of the
    list $s'$.

  \item[Case 2:] $x$ is an element of $s$.  \\ % 
    The list $s$ is only updated in two ways: i) an element of $s$ is
    determined not to be the majority element, in which case that
    element is discarded, and ii) the majority element is discovered,
    $r'$ is set to the singleton list containing the majority element,
    and $s'$ is set to $\emptyset$, \ie $x \in s' \union r'$.  In the
    former case, since $x$ is the majority key, it does not get
    discarded ans, thus, is an element of $s'$.  In the latter case,
    $x$ is the majority element, so $x \in r'$.  It follows that, $x
    \in s' \union r'$.

  \item[Case 3:] $x$ is an element of $r$.  \\ %
    In this case, no transition is enabled.
  \end{description}

  Thus, by the above case analysis, we have shown that in the
  post-state of the transition, $x$ is either the majority key of $b'$
  or is in the set $s' \union r'$, as needed.

  In the above analysis, we have proven that the property $P$ is
  indeed invariant.  Moreover, it is simple to see that the state
  machine terminates either when the sets $b$ and $s$ are both empty,
  or the set $r$ is non-empty; that is, when no more state transitions
  are enabled.  At that point, since $b = s = \emptyset$ the invariant
  implies that the majority key must be in $r$ if it indeed existed in
  the initial list of records $a$.
%\end{solution}
  }

\vspace{-\baselineskip}
\problempart %
Write down a recurrence for worst-case time this algorithm takes.  For
this part assume that the size of the working set at every stage is
even.

\solution{%
%\begin{solution}
  A recurrence for the worst-case time for this algorithm is
  $T(n)=T(n/2)+n/2$.  It is important to also specify, the boundary
  valuations of the running time; that is, the values for $T(0)$ and
  $T(1)$.  According to the algorithm, if we end up with $0$ records,
  we do nothing and if we end up with one record, we check if the key
  of that record is the majority key of the initial list of records;
  that is, $T(0) = 0$ and $T(1) = n$.
%\end{solution}
  }

\vspace{-\baselineskip}
\problempart %
Solve the recurrence you wrote down in part (b) to obtain an
asymptotic time bound ($\Theta$) for worst-case running time.  (We are
interested in the {\em order} of growth, not the exact constant.)

\solution{%
  %\begin{solution}
    The asymptotic time bound for the worst-case running time is
    $T(n)=T(n/2)+n/2=T(n/4)+n/4+n/2=...= 2 n - 3 = \Theta (n)$.
  %\end{solution}
  }

\vspace{-\baselineskip}
\problempart %
Argue that this time bound also holds without the assumption that the
working set at each stage is even.

\solution{%
%\begin{solution}
  If the set is odd, then $T(n)=T(n/2)+n/2+n=T(n/2)+3/2n$ which comes
  down to $T(n)= 4 n - 9 = \Theta (n)$.
%\end{solution}
  }

\end{problemparts}

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

%\clearpage 
\problem \textbf{Linear Recurrences}

Find closed-form solutions to the following linear recurrences.

\begin{problemparts}
  \vspace{-\baselineskip}
\problempart $x_{n} = 5 x_{n-1} - 6 x_{n-2} \quad (x_0 = 0, x_1 =
  1)$

\solution{%
%\begin{solution}
  The characteristic equation is $r^2 - 5 r + 6 = 0$.  The roots can
  be found with the quadratic formula:

\begin{eqnarray*}
  r_1 & = & 2 \\ r_2 & = & 3
\end{eqnarray*}

This implies a solution of the form

\begin{eqnarray*}
  x_n & = & A 2^n + B 3^n.
\end{eqnarray*}

Substituting the initial conditions into this general form gives a
system of linear equations:

\begin{eqnarray*}
  0 & = & A + B \\ 1 & = & 2 A + 3 B
\end{eqnarray*}

The solution to this system is $A = -1$ and $B = 1$.  Therefore, the
final solution to the recurrence is

\begin{eqnarray*}
  x_n & = & 3^n - 2^n.
\end{eqnarray*}
%\end{solution}
}

\vspace{-\baselineskip}
\problempart $x_{n} = 5 x_{n-1} - 8 x_{n-2} + 4 x_{n-3} \quad (x_0 =
1, x_1 = 2, x_2 = 3)$

\solution{%
%\begin{solution}
  The characteristic equation is $r^3 - 5 r^2 + 8 r - 4 = 0$.  Solving
  a cubic equation can be messy process, but in this case the roots
  are easy to find:

\begin{eqnarray*}
  r_1 & = & 2 \\ r_2 & = & 2 \\ r_3 & = & 1
\end{eqnarray*}

The general form of the solution is therefore

\begin{eqnarray*}
  x_n & = & A 2^n + B n 2^n + C.
\end{eqnarray*}

Substituting the initial conditions into this general form gives a
system of linear equations.

\begin{eqnarray*}
  1 & = & A + C \\ 2 & = & 2 A + 2 B + C \\ 3 & = & 4 A + 8 B + C
\end{eqnarray*}

The solution to this linear system is $A = 2$, $B = -\frac{1}{2}$, and
$C = -1$.  The complete solution to the recurrence is therefore

\begin{eqnarray*}
  x_n & = & 2^{n+1} - n 2^{n-1} - 1.
\end{eqnarray*}
%\end{solution}
}

\vspace{-\baselineskip}
\problempart (Fibonacci Plus) %
$x_{n} = x_{n-1} + x_{n-2} + 1 \quad (x_0 = 0, x_1 = 1)$

\solution{%
%\begin{solution}
  First, we find the general solution to the homogeneous recurrence.
  The characteristic equation is $r^2 - r - 1 = 0$.  The roots of this
  equation are:

\begin{eqnarray*}
  r_1 & = & \frac{1 + \sqrt{5}}{2} \\ r_2 & = & \frac{1 - \sqrt{5}}{2}
\end{eqnarray*}

Therefore, the solution to the homogeneous recurrence is of the form

\begin{eqnarray*}
  x_n & = & A \left( \frac{1 + \sqrt{5}}{2} \right)^n + B \left(
  \frac{1 - \sqrt{5}}{2} \right)^n.
\end{eqnarray*}

Next, we need a particular solution to the inhomogeneous recurrence.
Since the inhomogeneous term is constant, we guess a constant solution
$b$.

\begin{eqnarray*}
  b & = & b + b + 1 \\
  b & = & -1 
\end{eqnarray*}

Therefore, the inhomogeneous recurrence has the simple particular
solution $x_n = -1$.  The complete solution to the recurrence is the
homogeneous solution plus the particular solution:

\begin{eqnarray*}
  x_n & = & A \left( \frac{1 + \sqrt{5}}{2} \right)^n + B \left(
  \frac{1 - \sqrt{5}}{2} \right)^n - 1
\end{eqnarray*}

All that remains is to find the constants $A$ and $B$.  Substituting
the initial conditions gives a system of linear equations.

\begin{eqnarray*}
  0 & = & A + B - 1 \\ 1 & = & A \left( \frac{1 + \sqrt{5}}{2} \right)
  + B \left( \frac{1 - \sqrt{5}}{2} \right) - 1
\end{eqnarray*}

The solution to this linear system is:

\begin{eqnarray*}
  A & = & \frac{5 + 3 \sqrt{5}}{10} \\ B & = & \frac{5 - 3
    \sqrt{5}}{10}
\end{eqnarray*}

Therefore, the complete solution to the recurrence is

\begin{eqnarray*}
  x_n & = & %
  \left( \frac{5 + 3 \sqrt{5}}{10} \right) %
    \cdot \left( \frac{1 + \sqrt{5}}{2} \right)^n %
  + \left( \frac{5 - 3 \sqrt{5}}{10} \right) %
    \cdot \left( \frac{1 - \sqrt{5}}{2} \right)^n - 1.
  \end{eqnarray*}
%\end{solution}
}

\end{problemparts}

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

\clearpage
\problem \textbf{Injections, Surjections, and Bijections}
%[[[Source:  first two parts are standard, second two are from
%Velleman, p. 231, Ex. 6]]]

Let $f$ be a function from $A$ to $B$, and $g$ a function from $B$ to
$C$.  The composition $g \circ f$ is defined by:
$g \circ f (x) = g(f(x))$.

%[[[Check that my notation is consistent with what's been used in the
%class, in Rosen, etc.]]]

Determine whether each of the following statements is true or false.
If it's true, prove it.  If it's false, give a counterexample.

\begin{problemparts}

\vspace{-\baselineskip}
\problempart
If $f$ and $g$ are both injective then $g \circ f$ is injective.

\solution{%
  Let $a, a' \in A$, $b = f(a)$, $b' = f(a')$, $c = g \circ f (a)$,
  and $g \circ f (a')$.  It suffices to show that if $a = a'$ then $c
  = c'$.  Since $f$ is injective, if $a = a'$ then $b = b'$.
  Similarly since $g$ is injective, if $b = b'$ then $c = c'$.  It
  follows that, if $a = a'$ then $c = c'$.
  %
  }

\vspace{-\baselineskip}
\problempart
If $f$ and $g$ are both surjective then $g \circ f$ is surjective.

\solution{%
  Since $g$ is surjective, it is the case that for all $c \in C$ there
  exists an element $b \in B$ such that $g(b) = c$.  Similarly, since
  $f$ is surjective, it is the case that for all $b \in B$ there
  exists an element $a \in A$ such that $f(a) = b$.  Thus, it follows
  that for all $c \in C$, there exists some $a \in A$ such that $g
  \circ f (a) = c$; that is, $g \circ f$ is surjective.
  %
  }

\vspace{-\baselineskip}
\problempart
If $f$ is surjective and $g \circ f$ is injective then $g$ is injective.

\solution{%
  The proof is by contradiction.  Let $f$ be surjective and $g \circ
  f$ be injective and suppose that $g$ is \emph{not} injective.  Then,
  since $g$ is not injective, there exist $b, b' \in B, b \not = b'$
  such that $g(b) = g(b')$.  Moreover, since $f$ is surjective there
  exist $a, a' \in A, a \not = a'$ such that $f(a) = b$ and $f(a') =
  b'$.  It follows that, $g \circ f (a) = g \circ f (a')$ which
  implies that $g \circ f$ is not injective; that is, we have reached
  a contradiction.  It follows that our initial assumption must be
  false; that is, it is the case that $g$ is injective.
  %
  }

\vspace{-\baselineskip}
\problempart
If $g$ is injective and $g \circ f$ is surjective then $f$ is surjective.

\solution{%
  The proof is by contradiction.  Let $g$ be injective and $g \circ f$
  be surjective and suppose that $f$ is \emph{not} surjective.  Since
  $g$ is injective, it is the case that $|B| \leq |C|$.  Since $f$ is
  not surjective, there exists $b \in B$ for which there does not
  exist $a \in A$ such that $f(a) = b$; that is, the image of $f$ is a
  set $B' \subset B$, \ie $|B'| < |B| \leq |C|$.  It follows that $g
  \circ f$ can not be surjective; that is we have reached a
  contradiction.  It follows that our initial assumption must be
  false; that is, it is the case that $f$ is surjective.
  %
  }

\end{problemparts}

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

\clearpage
\problem \textbf{Counting Using Functions}

Determine the cardinality of the following: 
\begin{problemparts}
\vspace{-\baselineskip}
\problempart %
The number of binary relations on a set $A$ of $n$ elements.

\solution{%
  Consider the binary matrix representation of a binary relation on a
  set $A$ of $n$ elements where each element of the matrix indicates
  whether the corresponding elements of the set $A$ are related.
  Since each of these matrix elements can be either $0$ or $1$, the
  number of binary relations on a set $A$ of $n$ elements is equal to
  $2^{(n^2)}$.
  %
}

\vspace{-\baselineskip}
\problempart %
The number of different digraphs without self-loops for a set $V$ of
$n$ vertices.

\solution{%
  Consider the adjacency matrix of a digraph without self-loops for a
  set $V$ of $n$ vertices.  Since the digraph is restricted to have no
  self-loops, elements on the diagonal of the adjacency matrix are
  restricted to equal $0$.  However, the remaining elements of the
  adjacency matrix can be either $0$ or $1$.  It follows that the
  number of digraphs without self-loops for a set $V$ of $n$ vertices
  is equal to $2^{(n^2 - n)}$.
  %
}

\vspace{-\baselineskip}
\problempart %
The number of functions from $A$ to $B$, where $|A| = n$ and $|B| =
m$.

\solution{%
  Since the image of any element of $A$ is unique, it follows that
  each element of $A$ could map to any one element of $B$.  Thus, the
  number of functions from $A$ to $B$, where $|A| = n$ and $|B| = m$,
  is equal to $m^n$.
  %
}

\end{problemparts}

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

%\clearpage
\problem \textbf{Pigeonhole Principle}

\begin{problemparts}

\vspace{-\baselineskip}
\problempart
% problem 5, problem set 7, fall 1998

%[[[This one comes from Fall 98, pset 7, problem 5.  It might be nice
%to change the numbers.  Solutions are given there too.]]]

%Prove that among every set of $52$ integers, there exists a pair with
%sum or difference divisible by 100.

Prove that among every set of $18$ integers, there exists a pair with
sum or difference divisible by $32$.

\solution{%
  We assign each of the 18 numbers to one of 17 bins, defined as
  follows:

  First, we define 15 ``ordinary'' bins: bin 1 contains numbers
  congruent to 1 or 31 modulo 32, bin 2 contains numbers congruent to
  2 to 30 modulo 32, ..., bin 15 contains numbers congruent to 15 or
  17 modulo 32.  Now, we define two ``special'' bins: bin 0 contains
  numbers congruent to 0 modulo 32, and bin 16 contain numbers
  congruent to 16 modulo 32.

  By the Pigeonhole Principle, at least two out of the 18 numbers are
  assigned to the same bin.  If two numbers are assigned to an
  ordinary bin and are congruent modulo 32, then their difference is
  divisible by 32.  If two numbers are assigned to an ordinary bin and
  are not congruent modulo 32, then their sum is divisible by 32.  If
  two numbers are assigned to a special bin, then both their sum and
  their difference is divisible by 32.
  %
}

\clearpage 
%\vspace{-\baselineskip}
\problempart
% problem 6a, problem set 7, fall 1998

One of the 6.042 TAs has decided to conduct his next tutorial in the
following manner: he will arrange his $m$ students in alphabetical
order and hand out tutorial problems to each of the students such that
each student ends up with one or more problems.  The TA claims that
using such an arrangement, there is always a group of (one or more)
students that are consecutive in the alphabetical order and
collectively receive a number of problems that is a multiple of $m$.

As an example, consider a 6.042 tutorial with $m = 10$ students in
which the students are arranged in alphabetical order and each of
which receives $1, 2, 4, 8, 16, 16, 8, 4, 2, 1$ problems.  Then, since
the fourth, fifth, and sixth students have collectively received $40$
problems, the TA's claim holds.

Prove this claim for all $m$.

%The same pset, problem 6a.
%It's a very cute problem.
%But change not only the numbers but also the story.
%Or just make it about a sequence of $m$ consecutive positive natural
%numbers.

%Maybe say there are 120 students in the class.
%Arrange them in alphabetical order.
%Everyone owns one or more books. 
%Claim that there is some group of (one or more) students that are
%consecutive in alphabetical order, and whose total number of books is
%a multiple of 120.

\solution{%
  Let $P_i$ be the total number of problems given out to the first $i$
  students.  There are two cases.  In the first case, suppose that at
  least one of $P_1, P_2, \ldots, P_m$ is congruent to 0 modulo $m$.
  In particular, suppose that $P_j$ is congruent to 0 modulo $m$.
  This implies that the number of problems received by the first $j$
  students is a multiple of $m$, and so the claim holds.  In the
  second case, suppose that none of $P_1, P_2, \ldots, P_m$ is
  congruent to 0 modulo $m$.  Then each of the $m$ terms $P_1, P_2,
  \ldots, P_m$ is congruent to one of the $m-1$ values $1, 2, \ldots,
  m-1$ modulo $m$.  By the Pigeonhole Principle, there are at least
  two terms $P_j$ and $P_k$ that are congruent to the same value
  modulo $m$.  Thus students $j+1, j+2, \ldots, k$ received a total of
  $P_k - P_j$
  problems, which is a multiple of $m$.%
  }
\end{problemparts}

\end{problems}

\end{document}

\endinput

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Riemann's Zeta Function $\zeta(k)$ is defined to be the infinite summation:
\[
1+\frac1{2^k}+\frac1{3^k} \cdots = \sum_{j \ge 1} \frac1{j^k}
\]
Prove that 
\[
\sum_{k \ge 2} (\zeta(k)-1) = 1
\]

\textbf{Hint:} You may use (without proof) problem 2 from problem set~5.

\solution{%
  not done yet!
  }

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

\problem \textbf{Weighings}

Suppose you have a collection of 40 balls, of which you know that 39
have normal weight and one is abnormal~---~either heavy or light, but
you don't know which.

\begin{problemparts}
\vspace{-\baselineskip}
\problempart

Using a tree, describe a procedure, using weighings on a balance
scale, for determining both which ball is
the abnormal one, and whether it is heavy or light.
Your procedure should use the smallest number of weighings
possible.

\solution{%
  [[[I think 5 must work--- check me.  Does this turn out to be too
  complicated/detailed? ]]]
}

\vspace{-\baselineskip}
\problempart
Prove that no algorithm can be guaranteed to determine the answer in
fewer weighings.

\solution{%
  [[[I think that 4 is impossible; the method is as near the end of my
  lecture notes for lecture 13.]]]%
  }

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \textbf{False Proofs}

Determine why each of the following are false proofs.

\begin{problemparts}

\vspace{-\baselineskip}
\problempart

\[
\left( \sum_{j=1}^n a_j \right) \left( \sum_{k=1}^n 1/a_k \right) =
\sum_{j=1}^n \sum_{k=1}^n a_j/a_k =
\sum_{k=1}^n \sum_{k=1}^n a_k/a_k =
\sum_{k=1}^n \sum_{k=1}^n 1 =
\sum_{k=1}^n n = n^2
\]

\solution{%
  not done yet!
  }

\vspace{-\baselineskip}
\problempart



\end{problemparts}


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

\problem \textbf{Asymptotic notation}
% problem 4, problem set 5, fall 1997

Given that $f(x) = O(g(x))$, prove or disprove the following:

\bparts
\ppart
$2^{f(x)} = O(2^{g(x)})$

\solution{%
  The above does not hold. Let $f(x) = 2x$ and $g(x) = x$. Then $f(x)
  = O(g(x))$. Now $2^{f(x)} = 2^{2x} = 4^x$, and $2^{g(x)} = 2^x$, and
  $4^x\neq O(2^x)$. Indeed, $\frac{4^x}{2^x} = 2^x$, so the ratio
  grows without bound as $x$ grows~---~it is not bounded by a constant. %
  }

\ppart 
$f(x)^2 = O(g(x)^2)$

\solution{%
  The above does hold.  Since $f(x) = O(g(x))$, $\exists x_0,c$ such
  that $\forall x \geq x_0, |f(x)| \leq cg(x)$.  So, $\forall x \geq
  x_0, f(x)^2 \leq c^2g(x)^2$.  Therefore, there exist $x_0' = x_0$
  and $c' = c^2$ such that $\forall x \geq x_0', f(x)^2 \leq
  c'g(x)^2$.  So $f(x)^2 =
  O(g(x)^2)$. %
  }

\eparts

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

\vspace{-\baselineskip}
\problempart %
$x_{n} = 3x_{n-1} - 2 x_{n-2} + n \quad (x_0 = 0, x_1 = 1)$

\solution{%
%\begin{solution}
  First, we find the general solution to the homogeneous recurrence.
  The characteristic equation is $r^2 - 3r + 2 = 0$.  The roots of
  this equation are $r_1 = 1$ and $r_2 = 2$.  Therefore, the general
  solution to the homogeneous recurrence is

\begin{eqnarray*}
  x_n & = & A + B 2^n.
\end{eqnarray*}

Now we must find a particular solution to the recurrence, ignoring the
boundary conditions.  Since the inhomogeneous term is linear, we guess
a solution that is quadratic:

\begin{eqnarray*}
  an^2+bn+c & = & 3(a(n-1)^2+b(n-1)+c) - 2(a(n-2)^2+b(n-2)+c) + n \\ &
  = & an^2+2an-5a+bn+b+c+n \\ 0 & = & 2an - 5a + b + n
\end{eqnarray*}

This equation is solved by setting $a = -\frac{1}{2}$ and $b =
-\frac{5}{2}$.  Apparently, any value of $c$ gives a valid particular
solution; for simplicity, we choose $c = 0$.  Therefore, the
particular solution is:

\begin{eqnarray*}
  x_n & = & -\frac{1}{2}n^2 - \frac{5}{2} n
\end{eqnarray*}

The complete solution to the recurrence is the homogeneous solution
plus the particular solution:

\begin{eqnarray*}
  x_n & = & A + B 2^n -\frac{1}{2}n^2 - \frac{5}{2} n
\end{eqnarray*}

Substituting the initial conditions gives a system of linear
equations:

\begin{eqnarray*}
  0 & = & A + B \\ 1 & = & A + 2 B - 3
\end{eqnarray*}

The solution to this linear system is $A = -4$ and $B = 4$.
Therefore, the complete solution to the recurrence is

\begin{eqnarray*}
  x_n & = & 2^{n+2} -\frac{1}{2}n^2 - \frac{5}{2} n - 4.
\end{eqnarray*}
%\end{solution}
}

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

\problem \textbf{Injections, Surjections, and Bijections}
% problem 5, problem set 6, spring 1998

For each of the following functions, $f: \reals \rightarrow \reals$,
determine whether it is an injection, surjection, or bijection and
give the inverse if it exists.

\begin{problemparts}

\vspace{-\baselineskip}
\problempart $f(x) = \sin (x)$

\solution{%
%\begin{solution}
  $f(x) = \sin (x)$ is not an injection because it maps $0$ and $\pi$
  to $0$.  It is not a surjection because it maps $\reals$ onto
  $[-1,1]$.  Therefore it is not a bijection and does not have an
  inverse.
%\end{solution}
}

\vspace{-\baselineskip}
\problempart $f(x) = \frac{x+2}{x^2 + 4}$

\solution{%
%\begin{solution}
  $f(x) = {{x+2}\over{x^2 + 4}}$ is not an injection because it maps
  $0$ and $2$ to ${1}\over{2}$.  It is not a surjection because $1$
  has no pre-image.  $x^2 + 4 = x+2$ has no real solutions.  Therefore
  it is not a bijection and does not have an
  inverse.
%\end{solution}
}

\vspace{-\baselineskip}
\problempart

\begin{equation}
f(x) =
\begin{cases}
  {\ln x} & \text{if } x > 0,\\ %
  0 & \text{if } x = 0,\\ %
  {e^x} & \text{if } x < 0 %
\end{cases}
\end{equation}

\solution{%
%\begin{solution}  
  This function is not an injection because $ln {{1}\over{2}}$ and
  $e^{{1}\over{2}}$ both map to ${1}\over{2}$.  It is a surjection
  because for any $x \in \reals$, a pre-image of $x$ is $e^x$ for $x
  \neq 0$, and $0$ for $x=0$.
%\end{solution}
}

\vspace{-\baselineskip}
\problempart

$f(x) = x^3 + 2$

\solution{%
%\begin{solution}
  $f(x) = x^3 + 2$ is an injection because $x \neq y \rightarrow x^3
  \neq y^3 \rightarrow x^3 + 2 \neq y^3 + 2$.  The function is a
  surjection because for every $x \in \reals$ $\exists\; y =
  (x-2)^{{1}\over{3}}$.  Therefore $f$ is a bijection.  It's inverse
  is $(x-2)^{{1}\over{3}}$.
%\end{solution}
}

\end{problemparts}

