\documentclass[12pt,twoside]{article}

\def\handouttype{problemset}

\usepackage{psfig}
\usepackage{changebar}
%\newcommand{\cbstart}{\chgbarbegin}
%\newcommand{\cbend}{\chgbarend}

\input{macros-course}

\def\cent{{\not\!\mathrm{c}}}

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

\askaboutsolutions

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

\newcommand{\problembreak}{%
  \ifshowsolutions %
  \newpage
  \else
  \newpage
  \fi%
}

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

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\tutref}{tut7}
\newcommand{\tutnum}{7}
\newcommand{\tutdate}{March 17, 2000}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\handout{\tutref}{Mini-Quiz \tutnum}{\tutdate}

\begin{enumerate}
\item Write your name:

\bigskip

\item %
  (Rosen, Section 1.8, Problem 13) %
  Show that $2^n$ is $O(3^n)$ but that $3^n$ is not $O(2^n)$.

  \vspace*{3in}

\end{enumerate}

\newpage
\thispagestyle{empty}

\mbox{}

\setcounter{page}{0}

\newpage
\handout{\tutref}{Tutorial \tutnum~Problems}{\tutdate}

\begin{problems}

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

\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:} Recall from problem set~5, problem 2, that
$\sum_{k=2}^n {\frac{1}{k(k-1)}} = 1 - \frac{1}{n}$.

\solution{%
  \begin{eqnarray*}
    \sum_{k \ge 2} (\zeta(k)-1) %
    & = & \sum_{k \ge 2} \left[ \left( \sum_{j \ge 1} \frac{1}{j^k} \right) - 1 \right] \\
    & = & \sum_{k \ge 2} \sum_{j \ge 2} \frac{1}{j^k} \\
    & = & \sum_{j \ge 2} \sum_{k \ge 2} \frac{1}{j^k} \\
    & = & \sum_{j \ge 2} \frac{1}{j^2} \sum_{k \geq 0} \frac{1}{j^k} \\
    & = & \sum_{j \ge 2} \frac{1}{j^2} \cdot \frac{1}{1 - 1/j} \\
    & = & \sum_{j \ge 2} \frac{1}{j (j - 1)} \\
    & = & \lim_{n \rightarrow \infty} \sum_{j = 2}^{n} \frac{1}{j (j - 1)} \\
    & = & \lim_{n \rightarrow \infty} (1 - \frac{1}{n}) \\
    & = & 1
  \end{eqnarray*}
  }

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

\problembreak
\problem \textbf{Linear Recurrences}

Math Moose has discovered that the fluctuation in the price of stocks
in his portfolio (in particular the stock prices of start-up companies
that have recently gone public) satisfy a particular temporal
property.  The price fluctuation at any given day is twice that of the
previous day, plus four times that of the day before that, plus
negative eight times the day before that.  In order to test out his
discovery Math Moose has performed a series of tests of the following
nature: he buys one stock of a particular start-up company and
evaluates the price fluctuation on each successive day.  He has found
that the fluctuation of the stock price the day he buys the stock is
$f(0) = 0$, the next day it's $f(1) = 1$, and the day after that it's
$f(2) = 2$.  Given this information can you come up with a closed-form
solution for the price fluctuation of start-up stocks as discovered by
Math Moose?

\begin{problemparts}
  
  \problempart %
  Determine the linear recurrence, $f(n)$, corresponding to the
  fluctuation in the price of start-up company stocks in day $n$.
  What are the boundary conditions of $f(n)$ as discovered by Math
  Moose?

  \solution{%
    The linear recurrence , $f(n)$, corresponding to price fluctuation
    of a start-up stock in day $n$ is as follows:

    $$f(n) = 2 f(n-1) + 4 f(n-2) - 8 f(n-3)$$

    with $f(0) = 0$, $f(1) = 1$, and $f(2) = 1$.
    %
    }

  \problempart %
  Determine the characteristic equation of the linear recurrence
  $f(n)$ and find it's roots.  \textbf{Hint:} The characteristic
  equation has a repeated root.

  \solution{%
    In order to find the characteristic equation, we guess at the
    solution $f(n) = c a^n$.  By plugging in this solution to the
    linear recurrence above, we obtain the characteristic equation
    $r^3 - 2 r^2 - 4 r + 8 = 0$.  Since the characteristic equation
    has a repeated root, by plugging in $(r - r_{1,2})^2 (r - r_3) =
    0$ and equating coefficients, we obtain the roots $r_{1,2} = 2$
    and $r_3 = -2$.%
    }

  \problempart %
  Determine the recurrence solution.

  \solution{%
    The solution is of the general form:
    
    $$f(n) = c_1 2^n + c_2 n 2^n + c_3 (-2)^n$$

    and the coefficients $c_1$, $c_2$, and $c_3$ are determined from
    the boundary conditions $f(0) = 0$, $f(1) = 1$, and $f(2) = 2$.

    Plugging in for the boundary cases in the general form gives the
    following system of equations:
    
    \begin{eqnarray*}
      0 & = & c_1 + c_3 \\
      1 & = & 2 c_1 + 2 c_2 - 2 c_3 \\
      2 & = & 4 c_1 + 8 c_2 + 4 c_3 
    \end{eqnarray*}
    
    The solution to this system of equations is $c_1 = \frac{1}{8}$,
    $c_2 = \frac{1}{4}$, and $c_3 = -\frac{1}{8}$.  Therefore, the
    complete solution to the recurrence is:

    $$f(n) = \frac{1}{8} 2^n + \frac{1}{4} n 2^n - \frac{1}{8} (-2)^n$$
    }

  \problempart %
  After testing his theory out, Math Moose has discovered that he has
  to adjust his way of evaluating the fluctuation of the stock price
  of start-up company founded by MIT graduates.  He has noticed that
  MIT start-ups outperform other start-ups.  Thus, he adjusts his
  scheme so that the price fluctuation for MIT start-up companies is
  increased by a constant dollar amount equal to $3$ dollars each day.

  What is the resulting inhomogeneous linear recurrence corresponding
  to Math Moose's scheme?

  \solution{%
    The resulting recurrence is of the form:

    $$f(n) = 2 f(n-1) + 4 f(n-2) - 8 f(n-3) + 3$$
    
    %
    }

  \problempart %
  Find the particular solution to the resulting inhomogeneous linear
  recurrence.

  \solution{%
    Since we always choose a particular solution of the form of the
    extra term of the recurrence, we try the solution $f(n) = c$.
    Plugging into the resulting recurrence we get the equation:

    \[ c = 2 c + 4 c - 8 c + 3 \]
    
    Solving the equation for $c$ we get $c = 1$.  Thus, the particular
    solution of the inhomogeneous linear recurrence is $f(n) = 1$.
    %                         
    }

  \problempart %
  What is the complete solution to the resulting inhomogeneous linear
  recurrence?

  \solution{%
    The solution is of the general form:
    
    $$f(n) = c_1 2^n + c_2 n 2^n + c_3 (-2)^n + 1$$

    and the coefficients $c_1$, $c_2$, and $c_3$ are determined from
    the boundary conditions $f(0) = 0$, $f(1) = 1$, and $f(2) = 2$.

    Plugging in for the boundary cases in this general form gives the
    following system of equations:
    
    \begin{eqnarray*}
      0 & = & c_1 + c_3 + 1\\
      1 & = & 2 c_1 + 2 c_2 - 2 c_3 + 1 \\
      2 & = & 4 c_1 + 8 c_2 + 4 c_3 + 1
    \end{eqnarray*}
    
    The solution to this system of equations is $c_1 = -
    \frac{13}{16}$, $c_2 = \frac{5}{8}$, and $c_3 = -\frac{3}{16}$.
    Therefore, the complete solution to the recurrence is:

    $$f(n) = -\frac{13}{16} 2^n + \frac{5}{8} n 2^n - \frac{3}{16} (-2)^n + 1$$
    %
    }

  \problempart %
  Do you believe Math Moose's scheme for determining the price
  fluctuation of start-up stocks?

  \solution{%
    Must determine whether $f(n)$ is monotonically increasing...  If
    it is then that would not seem right because it would mean that
    the stock price monotonically increases.
    %
    }

\end{problemparts}

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

\problembreak
\problem \textbf{Pigeonhole Principle}

\begin{problemparts}

  \problempart %
  Let $A$ be any set of $n+1$ numbers from the set $\set{1, 2, \ldots,
    2 n}$.  Prove that there are always two numbers in $A$ such that
  one divides the other.

  \solution{%
    Ref. ``Proofs from THE BOOK''.

    We use the pigeonhole principle as follows: Let any number of $A$,
    $a$, be represented in the form $a = 2^k m$, where $m$ is an odd
    number between $1$ and $2n-1$.  Since there are $n+1$ numbers in
    $A$k but only $n$ different odd parts, there must be two numbers
    in $A$ with the same odd part.  Hence, one is a multiple of the
    other.
    %
    }

  \problempart %
  Let $A$ be any set of $n$ numbers from the set $\set{1, 2, \ldots, 2
    n}$.  Prove that there are \textbf{not} always two numbers in $A$
  such that one divides the other.

  \solution{%
    Ref. ``Proofs from THE BOOK''.

    Consider the set $A = \set{n+1, n+2, \ldots, 2n}$.  In this case,
    the smallest number $n+1$ could not possibly divide the others
    because it can not divide even the largest number $2n$ (unless $2n
    = n+1$, which is only true for $n = 1$), since $2(n+1) > 2n$.  It
    follows, that none of the numbers can divide any of the other
    numbers.
    %
    }

\end{problemparts}

\end{problems}

\end{document}

\endinput

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

\problem \textbf{Pigeonhole Principle}

Prove that in any sequence $a_1, a_2, \ldots a_{71}$ of $71$ distinct
real numbers, there exists either an increasing subsequence

$$a_{i_1}, a_{i_2}, \ldots, a_{i_8} \qquad (i_1 < i_2 < \ldots < i_8)$$

of length $8$, or a decreasing subsequence 

$$a_{j_1}, a_{j_2}, \ldots, a_{j_11} \qquad (j_1 > j_2 > \ldots > j_11)$$

of length $11$, or both.

\solution{%
  not done yet!
  }

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

\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

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

\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) = \frac{x+2}{x^2 + 4}$ is not an injection because it maps $0$
  and $2$ to $\frac{1}{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 {\frac{1}{2}}$ and
  $e^{\frac{1}{2}}$ both map to $\frac{1}{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)^{\frac{1}{3}}$.  Therefore $f$ is a bijection.  It's inverse
  is $(x-2)^{\frac{1}{3}}$.
%\end{solution}
  }

\end{problemparts}

