<s>[INST] Solve recurrence equations-homework extras Extras from my homework. The first one should be easier, but still hard enough.
1) $a_{n+3}-(3/2)a_{n+2}-a_{n+1}-(1/4)a_n=0$
2) $a_{n+3}-3a_{n+2}-3a_{n+1}+a_n=n^2+2^n$
 [/INST] Use Wilf's "generatingfunctionology" techniques. Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the recurrence by $z^n$ and sum over $n \ge 0$ to get for (1):
$$
\frac{A(z) - a_0 - a_1 z - a_2 z^2}{z^3}
  - \frac{3}{2} \frac{A(z) - a_0 - a_1 z}{z^2}
  - \frac{A(z) - a_0}{z}
  - \frac{1}{4} A(z) = 0
$$
Solve for $A(z)$, split into partial fractions. The expansions:
$$
(1 - u)^{-m} = \sum_{n \ge 0} \binom{n + m - 1}{m - 1} u^n
$$
will be all that is needed. It works with complex roots too.
For (2) you'll need:
$$
\sum_{n \ge 0} n^2 z^n
  = z \frac{d}{dz} ( z \frac{d}{dz} \sum_{n \ge 0} z^2 )
  = z \frac{d}{dz} ( z \frac{d}{dz} \frac{1}{1 - z} )
  = \frac{z + z^2}{(1 - z)^3}
$$
and also:
$$
\sum_{n \ge 0} 2^n z^n
  = \sum_{n \ge 0} (2 z)^n
  = \frac{1}{1 - 2 z}
$$
</s>