\magnification=\magstep1
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Discussion 3 -- Inhomogeneous
Linear Recurrences With Constant Coefficients}
\centerline{March 18, 2005}
\bigskip
\noindent
{\it Background}  
\bigskip
Many of the most common recurrences that we need to solve
in combinatorics are {\it linear recurrences with constant
coefficients}, of the form:
$$h_n = a_1 h_{n-1} + a_2 h_{n-2} + \cdots + a_k h_{n-k} + b(n)\leqno(1)$$
We looked at the case $b(n) = 0$ (the homogeneous recurrences) last time.
Today, we will investigate recurrences with $b(n) \ne 0$ in some detail.
\bigskip
\noindent
{\it Discussion Questions}
\bigskip
\noindent
A)  The basis for the treatment of the inhomogeneous case is
a fact that is parallel to patterns you have seen in Linear Algebra
(and possibly Differential Equations too!).
Show that if $h_n, p_n$ are any two solutions of the same 
inhomogeneous recurrence (1):
$$\eqalign{
h_n &= a_1 h_{n-1} + a_2 h_{n-2} + \cdots + a_k h_{n-k} + b(n)\cr
p_n &= a_1 p_{n-1} + a_2 p_{n-2} + \cdots + a_k p_{n-k} + b(n)\cr}$$
then the difference sequence $g_n = h_n - p_n$ is a solution of the 
homogeneous recurrence 
$$g_n = a_1 g_{n-1} + a_2 g_{n-2} + \cdots + a_k g_{n-k}\leqno(2)$$
associated to (1).  (Note:  the coefficients on the various
terms from the sequence are the same, but the $b(n)$ term
has been replaced by zero.)
\bigskip
\noindent
B) Suppose we can find the {\it general solution} $g_n$ of (2)
by the methods we discussed in class
last time, and that we know some ``particular solution''
of (1) like $p_n$ above.  What does that say about solving (1)?  Explain.
\bigskip
\noindent
To determine ``particular solutions'', we will use the following 
``rules of thumb'' based on the form of the function $b(n)$:
\bigskip
\item{$\bullet$}  If $b(n) = b_\ell n^\ell + \cdots + b_1 n + b_0$,
then try a particular solution of the same form
$$p_n = P_\ell n^\ell + \cdots + P_1 n + P_0$$
but with {\it undetermined coefficients} $P_k$.  (Be sure you 
understand the notation here: $p_n$ is the sequence giving
the particular solution; $P_k$ with the capital letters are
the undetermined coefficients that we want to solve for.)
\item{$\bullet$}  If $b(n) = q^n$, then try a particular solution
$p_n = P q^n$ (same $q$, of course!)
\bigskip
\noindent
Then in both cases, substitute into (1) and try to determine the constants
to make $j_n$ a solution of (1) for all $n$.

\bigskip
\noindent
C)  For instance, find a particular solution of 
$$h_n = 6h_{n-1} - 9h_{n-2} + 2n.\leqno(3)$$
Then use that and the solution of the associated homogeneous
recurrence to solve (3) with the initial conditions
$h_0 = 1, h_1 = 0$.
\bigskip
\noindent
D)  The rules of thumb above do not always ``work'' (in particular
they can fail if the proposed particular solution actually solves
the homogeneous equation.  Show that this happens, for instance
for the recurrence
$$h_n = 5h_{n-1} - 6h_{n-2} + 2^n$$
Find a particular solution in this case of the form $p_n = P\cdot n 2^n$ for 
some constant $P$.  Then use that and the solution of the associated 
homogeneous recurrence to solve (3) with the initial conditions
$h_0 = 1, h_1 = 0$.
\bigskip
\noindent
{\it Assignment}
\bigskip
Group writeups due in class on Wednesday, March 23.    
\bye