MATH 357 – Combinatorics Solutions for Problem Set 7 March 31, 2017

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) = ∑_{n=0}^{∞} R_{n}x^{n}, we have

R(x) = R_{0} + R_{1}x + R_{2}x^{2} + R_{3}x^{3} + R_{4}x^{4} + ⋯
2xR(x) =  2R_{0}x + 2R_{1}x^{2} + 2R_{2}x^{3} + 2R_{3}x^{4} + ⋯
35x^{2}R(x) =  35R_{0}x^{2} + 35R_{1}x^{3} + 35R_{2}x^{4} + ⋯

so

(1 − 2x − 35x^{2})R(x) = (R_{1} − 2R_{0})x = x ⇒ 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}).

6.2.8. 6.3.9. 6.3.13. 6.5.18. 6.5.20.