\documentclass {exam}
\pagestyle {headandfoot}
\lfoot {\oddeven {}{Page \thepage \space of \numpages }}
\cfoot {}
\rfoot {\oddeven {Page \thepage \space of \numpages }{}}
\pointsinmargin \boxedpoints \addpoints
\newcommand \solution {\par \textbf {Solution:}\enspace }
\begin {document}
\noindent \textbf{MATH 112}\hfill
\textbf{Week 5 homework}\hfill
\textbf{Not due 2003 August 29}
\vskip 12pt plus 4pt minus 4pt
\begin {questions}
\question
Consider the recurrence equation $a_{n+2} = 4a_{n+1} - 4a_{n}$.
\begin {parts}
\part
Show that $a_{n} = 2^{n}(1 + n)$ is a solution of this recurrence equation.
\solution
If $a_{n} = 2^{n}(1 + n)$,
then $a_{n+2} = 2^{n+2}(1 + (n + 2)) = 2^{n}2^{2}(n + 3) = 2^{n}(4n + 12)$.
Meanwhile, $4a_{n+1} - 4a_{n}
= 4 \cdot 2^{n+1}(1 + (n + 1)) - 4 \cdot 2^{n}(1 + n)
= 4 \cdot 2^{n}2(n + 2) - 4 \cdot 2^{n}(n + 1)
= 2^{n}(8n + 16) - 2^{n}(4n + 4) = 2^{n}(4n + 12)$.
These are the same, so we have a solution.
\part
Find the most general solution of this recurrence equation.
\solution
This is a linear homogeneous recurrence equation with constant coefficients,
and the characteristic polynomial equation is $x^2 = 4x - 4$.
The roots of this equation are $r_{0} = 2$ and $r_{1} = 2$ again.
Thus the basic solutions to the equation are $2^{n}$ and $n2^{n}$.
Therefore the general solution is $c_{0}2^{n} + c_{1}n2^{n}$.
\end {parts}
\question
Consider the recurrence equation $a_{n+1} = 2a_{n} + n$.
\begin {parts}
\part
Find one solution to this recurrence equation.
\solution
This is a linear recurrence equation with constant coefficients
whose nonhomogeneous part is a polynomial ($n$) of degree $1$.
Thus there some polynomial of degree $1$ is a solution.
Arbitrarily let this solution take the form $p_{n} := b_{1}n + b_{0}$.
Then $p_{n+1} = b_{1}(n + 1) + b_{0} = b_{1}n + b_{1} + b_{0}$.
Meanwhile, $2p_{n} + n = 2(b_{1}n + b_{0}) + n = (2b_{1} + 1)n + 2b_{0}$.
Since these polynomials are to be equal for all values of $n$,
we must have $b_{1} = 2b_{1} + 1$ and $b_{1} + b_{0} = 2b_{0}$.
Then $b_{1} = -1$ and so $b_{0} = -1$ also.
Therefore one solution is $-n - 1$.
\part
Find the most general solution
to the related recurrence equation $a_{n+1} = 2a_{n}$.
\solution
This is the homogeneous part of the original equation.
Its characteristic polynomial equation is $x = 2$,
whose unique root is of course $r = 2$.
Thus the basic solution for the equation is $2^{n}$,
and the general solution is $h_{n} = c2^{n}$.
\part
Find the most general solution to the original recurrence equation.
\solution
Combining the results of the previous sections,
this is simply $h_{n} + p_{n} = c2^{n} - n - 1$.
\end {parts}
\end {questions}
\end {document}
