\newcommand{\ig}[1]{}

\documentclass[12pt,letterpaper]{article}

\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{fullpage}
\usepackage[plain,linesnumbered]{algorithm2e} %algo2e for compatibility

\title{Recitation 14}
\author{Taylor Spangler}

\begin{document}
\maketitle
\begin{itemize}
\item Questions about lecture / homework so far?

\item
7.1.9d) Use backwards substitution to solve $a_n = a_{n-1}+2n+3$, when $a_0 = 4$.

\begin{eqnarray*}
a_n & = & a_{n-1}+2n+3 \\
 & = & (a_{n-2} + 2(n-1) + 3) + 2n + 3 \\
 & = & a_{n-2} + 2n - 2 + 3 + 2n + 3 \\
 & = & a_{n-2} + 4n + 2(3) - 2 \\
 & = & (a_{n-3} + 2(n-2) + 3) + 4n + 2(3) - 2 \\
 & = & a_{n-3} + 2n - 4 + 3 + 4n + 2(3) - 2 \\
 & = & a_{n-3} + 6n + 3(3) - 2 - 4 \\
 & = & (a_{n-4} + 2(n-3) + 3) + 6n + 3(3) - 2 - 4 \\
 & = & a_{n-4} + 2n - 6 + 3 + 6n + 3(3) - 2 - 4 \\
 & = & a_{n-4} + 8n + 4(3) - 2 - 4 - 6 \\
 & = & \ldots \\
 & = & a_{n-n} + 2n(n) + n(3) - 2 - 4 - 6 - \ldots - 2(n-1) \\
 & = & a_{0} + 2n^2 + 3n - \sum_{i = 1}^{n-1} 2i \\
 & = & a_{0} + 2n^2 + 3n - 2\frac{(n-1)(n-1+1)}{2} \\
 & = & a_{0} + 2n^2 + 3n - n(n-1) \\
 & = & a_{0} + 2n^2 + 3n - n^2 + n \\
 & = & n^2 + 4n + 4
\end{eqnarray*}

\item Find the solution to the recurrence relation: 
\begin{eqnarray*}
a_n &= & 2 a_{n-1} + 8 a_{n-2}\\
a_0 &= & 3\\
a_1 &= & 4
\end{eqnarray*}

This relation is a linear homogeneous recurrence relation of degree~2
because:
\begin{itemize}
\item
The right-hand side has only multiples of previous terms of the
sequence and coefficients are all constants. Therefore, it is linear.

\item
No terms occur that are not multiples of $a_j$ (i.e., no non-recursive
cost). Therefore, it is homogeneous.

\item
It is expressed in terms of the $(n-2)^{th}$ term of the
sequence. Therefore, it is of degree~2).
\end{itemize}

We know that a solution to solve this recurrence relation is of the
form $a_n = r^n$ where $r$ is some real constant.  Replacing the
solution in the recurrence relation, we get:
\[r^n = 2 r^{n-1} + 8 r^{n-2}.\]
Dividing by $r^{n-2}$, we get:
\[r^2 = 2 r^1 + 8.\]  
Thus, the \emph{characteristic equation} of this recurrence relation
is:
\[r^2 - 2r - 8 = (r+2)(r-4) = 0.\]  
This characteristic equation has the roots $r_1 = -2$ and $r_2 = 4$;
Therefore, the solution of the recurrence relation is
\[a_n = \alpha_1 (-2)^n + \alpha_2 4^n.\]
Plugging in our initial conditions we get
\begin{eqnarray*}
3 & = & \alpha_1 + \alpha_2 \\
4 & = & -2 \alpha_1 + 4 \alpha_2
\end{eqnarray*}
Solving for $\alpha_1 = 3 - \alpha_2$, we get $4 = -2(3 -
\alpha_2) + 4 \alpha_2 \Rightarrow 4 = -6 + 2 \alpha_2 + 4 \alpha_2
\Rightarrow \frac{5}{3} = \alpha_2$.
Therefore, $\alpha_1 = \frac{4}{3}$ and $\alpha_2 = \frac{5}{3}$.

Putting the values of $\alpha_1, \alpha_2$ back in the solution form,
we obtain the following solution of the recurrence relation given the
boundary conditions
\[a_n = \frac{4}{3} (-2)^n + \frac{5}{3} 4^n.\]

\item
Solve the following linear non-homogeneous recurrence relation: 
\begin{eqnarray}
a_n &=& 2 a_{n-1} - 8 a_{n-2} + n\\
a_0 &=& 3\\
a_1 &=& 4
\end{eqnarray}
We notice that $f(n)$ is polynomial $n$. We will solve this problem
using Theorem~6 on page~469, which covers this case, the case that
$f(n)$ is an exponential in $n$, and the case where $f(n)$ is a
product of a polynomial and an exponential in $n$.

First, we solve the associated linear {\em homogeneous\/} recurrence
relation, which happens to be the one above :-).  Its solution is:
\[a_n = \alpha_1 (-2)^n + \alpha_2 4^n.\] 
Next, we find a particular solution for the given non-homogeneous
term.  Theorem~6 applies to $f(n)$ of the form:
\[f(n) = (b_t n^t + b_{t-1}n^{t-1} + \ldots + b_1n + b_0) s^n.\]
In our case, $f(n) = n$ and $s$ is 1.  Since our $s$ is \emph{not} a
root of our characteristic equation (*relief*), there is a particular
solution of the form:
\[a^p = (p_tn^t+ p_{t-1}n^{t-1}+ \ldots +p_1n + p_0)s^n.\]
For us, the particular solution is $a^p = p_1n + p_0$. Plugging the particular solution in Equation~(1), we get:
\begin{eqnarray*}
a^p = p_1n + p_0 &=& 2 (p_1 (n-1) + p_0) - 8 (p_1 (n-2) + p_0) + n\\
& =& 2p_1n - 2p_1 + 2p_0 - 8p_1n + 16 p_1 - 8p_0 + n\\
\end{eqnarray*}
Moving all terms to one side of the equation, we get:
\[(7p_1-1)n + (-14p_1 + 7p_0) = 0.\]
Given that $n \neq 0$, we must have the following:
\begin{eqnarray*}
7p_1-1 = 0\\
-14p_1 + 7p_0 = 0 
\end{eqnarray*}
Now, $7p_1 - 1 = 0 \Rightarrow 7p_1 = 1 \Rightarrow p_1 =
\frac{1}{7}$. \\
Further, $-14p_1 + 7 p_0 = 0 \Rightarrow -14(\frac{1}{7}) + 7 p_0 = 0
\Rightarrow -2 + 7p_0 = 0 \Rightarrow 7p_0 = 2 \Rightarrow p_0 =
\frac{2}{7}$.  We have thus found the particular solution: have $a^p = \frac{1}{7}n + \frac{2}{7}$.
Therefore,
\begin{eqnarray*}
a_n &=& a^h + a^p\\
a_n &=& (\alpha_1 (-2)^n + \alpha_2 4^n) + (\frac{1}{7}n + \frac{2}{7}).
\end{eqnarray*}
To determine the values of $\alpha_1, \alpha_2$, we plug in our
initial conditions:
\begin{eqnarray*}
3 & = & \frac{2}{7} + \alpha_1 + \alpha_2 \\
4 & = & \frac{1}{7} + \frac{2}{7} + -2 \alpha_1 + 4 \alpha_2
\end{eqnarray*}
Or:
\begin{eqnarray*}
\frac{19}{7} & = & \alpha_1 + \alpha_2 \\
\frac{25}{7} & = & -2 \alpha_1 + 4 \alpha_2
\end{eqnarray*}
Solving for $\alpha_1 = \frac{19}{7} - \alpha_2$, we get $\frac{25}{7} = -2(\frac{19}{7} - \alpha_2) + 4 \alpha_2
\Rightarrow \frac{25}{7} = -\frac{38}{7} + 2 \alpha_2 + 4 \alpha_2 \Rightarrow \frac{63}{7} = 6 \alpha_2 \Rightarrow \frac{63}{42} = \alpha_2$
Replacing $\alpha_2$ by its value, we get $\alpha_1 = \frac{-13}{42}$.

Replacing $\alpha_1, \alpha_2$, we get 
\[a_n = \frac{1}{7}n + \frac{2}{7} + \frac{63}{42} (-2)^n + \frac{-13}{42}
4^n.\]

\item
Give the asymptotic characterization for $T(n) = 3T(n/4) + 8n^3$.

Remember Master Theorem, when we have $T(n) = aT(n/b) + f(n)$ where:
\begin{itemize}
\item
$T(n)$ is monotone
\item
$f(n) \in \Theta(n^d)$ where $d \geq 0$, 
\item
$b$ is a constant
\end{itemize}
we can use it to classify our recurrence relation as follows:

$T(n) $ is $ \begin{cases}
\Theta(n^d) & a < b^d \\
\Theta(n^d \log n) & a = b^d \\
\Theta(n^{\log_b a}) & a > b^d
\end{cases}$

Therefore, we can use Master's theorem and $a = 3$, $b = 4$ and
$d=3$. Therefore, $T(n)$ is $\mathcal{O}(n)$ because $a < b^d (3 < 64)$.

\item (Last 10 minutes) Bonus quiz

\end{itemize}

\end{document}