\documentclass[11pt]{article}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\usepackage{latexsym,amsmath,amssymb,epsfig}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.0in}
\begin{document}
\centerline{MATH 357 -- Combinatorics}
\centerline{Solutions for Problem Set 7}
\centerline{March 31, 2017}
\vskip 10pt
\noindent
6.2.6.  From the recurrence $R_n = 2R_{n-1} + 35R_{n-2}$, with initial conditions $R_0 = 0$ and
$R_1 = 1$, if $R(x) = \sum_{n=0}^\infty R_n x^n$, we have
\begin{eqnarray*}
R(x) &=& R_0 + R_1 x + R_2 x^2 + R_3 x^3 + R_4 x^4 + \cdots \\
2xR(x)&=& \qquad 2R_0 x + 2R_1 x^2 + 2R_2 x^3 + 2R_3 x^4 + \cdots\\
35x^2 R(x) &=& \qquad\qquad\quad 35R_0 x^2 + 35R_1 x^3 + 35R_2 x^4 + \cdots
\end{eqnarray*}
so 
$$(1 - 2x - 35 x^2)R(x) = R_0 + (R_1 - 2R_0)x \Rightarrow R(x) = \frac{x}{1 - 2x - 35x^2}.$$
By partial fractions, 
$$\frac{x}{1 - 2x - 35x^2} = \frac{A}{1 - 7x} + \frac{B}{1 + 5x}$$
with $x = A(1 + 5x) + B(1 - 7x)$, so $A = \frac{1}{12}$ and $B = \frac{-1}{12}$.  From 
the geometric series expansions:
$$R_n = \frac{1}{12}(7^n - (-5)^n).$$   
\vskip 10pt
\noindent
6.2.8.  We follow the same method as in 6.2.6.  However, now the recurrence is of 3rd
order so we continue to $x^3 R(x)$ to get the combination that will cancel:
 From the recurrence $R_n = 5R_{n-1} + 29R_{n-2} - 105R_{n-3}$, with initial conditions $R_0 = 0$ and
$R_1 = R_2 = 1$, if $R(x) = \sum_{n=0}^\infty R_n x^n$, we have
\begin{eqnarray*}
R(x) &=& R_0 + R_1 x + R_2 x^2 + R_3 x^3 + R_4 x^4 + \cdots \\
-5xR(x)&=& \qquad -5R_0 x - 5R_1 x^2 - 5R_2 x^3 - 5R_3 x^4 + \cdots\\
-29x^2 R(x) &=& \qquad\qquad\quad -29R_0 x^2 - 29R_1 x^3 - 29R_2 x^4 + \cdots\\
105x^3R(x) &=& \qquad\qquad\qquad\qquad\qquad 105R_0 x^3 + 105R_1 x^4 + \cdots
\end{eqnarray*}
so 
$$(1 - 5x - 29 x^2 + 105x^3)R(x) = R_0 + (R_1 - 5R_0)x + (R_2 - 5R_1 - 29 R_0)x^2 \Rightarrow R(x) = \frac{x - 4x^2}{1 - 5x - 29x^2 + 105x^3}.$$
By partial fractions, 
$$\frac{x - 4x^2}{1 - 5x - 29x^2 + 105x^3} = \frac{A}{1 - 3x} + \frac{B}{1 + 5x} + \frac{C}{1 - 7x}$$
with 
$$x - 4x^2 = A(1 + 5x)(1 - 7x) + B(1 - 3x)(1 - 7x) + C(1 - 3x)(1 + 5x),$$ 
so $A = \frac{1}{32}$, $B = \frac{-3}{32}$, and $C = \frac{1}{16}$.  From 
the geometric series expansions:
$$R_n = \frac{1}{32}(3^n - 3\cdot (-5)^n + 2\cdot 7^n).$$   
\vskip 10pt
\noindent
6.3.9.  The characteristic polynomial is $1 - x - x^2$, which factors as
$$1 - x - x^2 = \left(1 - \frac{1 + \sqrt{5}}{2} x\right)\left(1 - \frac{1 - \sqrt{5}}{2} x \right).$$
Therefore the sequence will have the form 
$$F_n = c_1 \left(\frac{1 + \sqrt{5}}{2}\right)^n + c_2 \left(\frac{1 - \sqrt{5}}{2}\right)^n$$
for some constants $c_1, c_2$.  Note that $\alpha_1 = \frac{1 + \sqrt{5}}{2} \doteq 1.618$ and 
$\alpha_2 = \frac{1 - \sqrt{5}}{2} \doteq -.618$, hence $|\alpha_1| > |\alpha_2|$.  
Then $|\alpha_2/\alpha_1| < 1$, so $(\alpha_2/\alpha_1)^n \to 0$
as $n \to \infty$.   It
follows that as long as $c_1 \ne 0$ (that's the ``genericity condition'' you need for the statement
given in the problem to be true), 
$$\lim_{n\to\infty} \frac{F_n}{F_{n-1}} = \alpha_1 = \frac{1 + \sqrt{5}}{2}$$
like this:  we have
$$\frac{F_n}{F_{n-1}} = \frac{c_1 \alpha_1^n + c_2\alpha_2^n}{c_1 \alpha_1^{n-1} + c_2 \alpha_2^{n-1}}.$$
Multiply the top and bottom by $\frac{1}{\alpha_1^{n-1}}$:
$$\frac{F_n}{F_{n-1}} = \frac{c_1 \alpha_1 + c_2\alpha_2 \cdot \left(\frac{\alpha_2}{\alpha_1}\right)^{n-1}}
{c_1 + \left(\frac{\alpha_2}{\alpha_1}\right)^{n-1}}.$$
Now let $n\to\infty$.  The $(\alpha_2/\alpha_1)^{n-1}$ terms go to zero, leaving
$$\frac{c_1 \alpha_1}{c_1} = \alpha_1.$$
However, note that if $c_1 = 0$, then the ratio $F_n/F_{n-1}$ will equal $\alpha_2$ for all $n$.  
\vskip 10pt
\noindent
6.3.13.  The characteristic polynomial is $1 - 7x - 5x^2 + 75x^3 = (1 + 3x)(1 - 5x)^2$.  Hence
the general solution is 
$$R_n = A (-3)^n + (B + C n)5^n$$
for some constants $A,B,C$.  From the initial conditions
$$R_0 = 0 = A + B, R_1 = 0 = -3A + 5B + 5C, R_2 = 1 = 9A + 25B + 50C$$
Solving this system of linear equations, we find
$$A = \frac{1}{64}, B = \frac{-1}{64}, C = \frac{1}{40}.$$
Hence
$$R_n = \frac{1}{64}\cdot (-3)^n + \left(\frac{-1}{64} + \frac{1}{40}n\right)\cdot 5^n$$
\vskip 10pt
\noindent
6.5.18.  The solutions of the second order homogeneous recurrence $R_n = 6R_{n-1} + 7R_{n-2}$
are determined by the characteristic polynomial, $1 - 6x - 7x^2 = (1 + x)(1 - 7x)$, so they
are of the form $R_n = A\cdot (-1)^n + B\cdot 7^n$.  Because the inhomogeneous
term is $g(n) = n^2 + 3n + 5$, a polynomial function of $n$, the table on page 187 
indicates we should look for a particular solution of the form $C n^2 + Dn + E$.
So our ``candidate solution'' is 
$$R_n = A\cdot (-1)^n + B\cdot 7^n + Cn^2 + Dn + E.$$
We have $R_0 = R_1 = 1$, so $R_2 = 28$, $R_3 = 198$, $R_4 = 1417$.  
Therefore 
\begin{eqnarray*}
A + B + E &=& 1\\
-A + 7B + C + D + E &=& 1\\
A + 49B + 4C + 2D + E &=& 28\\
-A + 343B + 9C + 3D + E &=& 198\\
A + 2401B + 16C + 4D + E &=& 1417.
\end{eqnarray*}
The solution has $A = \frac{47}{32}$, $B = \frac{511}{864}$, $C = \frac{-1}{12}$, 
$D = \frac{-19}{36}$, and $E = \frac{-229}{216}$.
\vskip 10pt
\noindent
6.5.20.  The solutions of the second order homogeneous recurrence $R_n = 8R_{n-1} - 15R_{n-2}$
are determined by the characteristic polynomial, $1 - 8x + 15 x^2 = (1 - 3x)(1 - 5x)$, so they
are of the form $R_n = A\cdot 3^n + B\cdot 5^n$.  Because the inhomogeneous
term is $g(n) = 3^n$, an exponential in $n$ {\it that appears in the 
homogeneous solution}, the table on page 187 
indicates we should look for a particular solution of the form $C n 3^n$.
So our ``candidate solution'' is 
$$R_n = A\cdot 3^n + B\cdot 5^n + C\cdot n 3^n.$$
We have $R_0 = R_1 = 1$, so $R_2 = -7 + 9 = 2$.  
Therefore 
\begin{eqnarray*}
A + B  &=& 1\\
3A + 5B + 3C = 1\\
9A + 25B + 18C = 2\\
\end{eqnarray*}
The solution has $A = \frac{-1}{4}$, $B = \frac{5}{4}$, $C = \frac{-3}{2}$.
\end{document}
