\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 12} \author{Created by Taylor Spangler, Adapted by Beau Christ} \date{\today} \begin{document} \maketitle \begin{itemize} \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 {\em You are not responsible for solving non-homogeneous recurrence relations.}\\ 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^3)$ because $a < b^d (3 < 64)$. \end{itemize} \end{document}