\documentclass[12pt]{article}
\textwidth = 6.7 in
\textheight = 9.2 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.2 in
\headheight = 0.0 in
\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in

\usepackage{amsmath,amssymb,enumerate}
%\def\rmdefault{bch} % Use Charter for main text font.

% =========================================================
\begin{document}

\begin{center}
{\LARGE
\textbf{CS 173: Discrete Structures, Fall 2009}
\\
\textbf{Homework 7}
\\[1ex]}
\end{center}

This homework contains 5 problems worth a total of 42 regular points.
It is due on Friday, October 23 at noon.   Put your homework in
the appropriate dropbox in the Siebel basement.


\begin{enumerate}
%----------------------------------------------------------------------
\item 
\textbf{Big-O proofs [8 points]}

\begin{enumerate}
\item Prove that $\frac{x^3 + 2x}{2x+1}$ is $O(x^2)$.   
\item Use a proof by contradiction to show that $5^n$ is not $O(3^n)$.   
\end{enumerate}


%----------------------------------------------------------------------
\item 
\textbf{Unrolling [8 points]} 

Use unrolling to find a closed form for the function $f: \mathbb{N} \rightarrow \mathbb{R}$ 
defined by

\begin{itemize}
\item $f(0) = 0$
\item $f(n) = 5f(n-1) + 1$ for all $n \ge 1$
\end{itemize}

Show at least three steps of unrolling, show the unrolling pattern 
compactly using a summation, then convert to a simple algebraic equation.
Hint: you may need to consult a table of closed-forms
for familiar summations, e.g. the one in Rosen section 2.4.


%----------------------------------------------------------------------
\item 
\textbf{Recursion trees [8 points]} 

Consider the following recurrence:

\begin{itemize}
\item $T(1) = d$
\item $T(n) = T(n/3) + T(2n/3) + cn$
\end{itemize}

where $c$ and $d$ are constants.   Let's analyze $T$ when the input $n$
is a power of 3.   

  \begin{enumerate}
    \item Draw a recursion tree for $T$, in which each node shows the
contribution of the non-recursive term $cn$.   
    \item How high is this tree (exact height, not just big-O)?
    \item Use the tree to derive a closed-form solution for $T$, up to
big-O.
  \end{enumerate}

Hint: see lecture 22 for examples.   In part (c), ``up to big-O'' means
that your solution should have the form ``$T(n)$ is $O(xxx)$'' and,
therefore, you can ignore low-order terms and constant multipliers
in your solution.

\newpage
%----------------------------------------------------------------------
\item 
\textbf{``Strong'' induction [8 points]} 

Suppose that $f:\mathbb{Z}^+ \rightarrow \mathbb{Z}$ is defined by

\begin{itemize}
\item $f(1) = 3$
\item $f(2) = 5$
\item $f(n) = 3f(n-1) - 2f(n-2)$ for all $n \ge 3$.
\end{itemize}

Use strong induction to show that $f(n) = 2^n + 1$ for every positive integer $n$.
Hint: you must use strong induction, because that's the main point of this
problem.   

%----------------------------------------------------------------------
\item 
\textbf{Induction with an inequality [10 points]} 

Use induction to prove that the following equation holds for
all integers $n \ge 2$:

$$\sum_{k=n+1}^{2n} \frac{1}{k} \ge \frac{7}{12}$$


\end{enumerate}

\end{document}
