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$
 A: These are linear difference equations. There is a general theory about them. 
For the homogeneous equation 1) make the "Ansatz" $a_n:=C\ \lambda^n$ $\ (n\geq 0)$. There will be at most three admissible $\lambda$'s, called eigenvalues of 1). Assuming you found three different such $\lambda_i$ the general form of the solution of 1) is
$$a_n\ =\ C_1\lambda_1^n +C_2\lambda_2^n+C_3\lambda_3^n\qquad(n\geq 0)$$
with arbitrary constants $C_i$.
As for the inhomogeneous equation 2), a basic principle says that the general solution of 2) can be written as the sum of the general solution of 1) (which we already have) and a single solution of 2) found by inspired guessing. Looking at the right side of 2) an inspired guess is the "Ansatz"
$$a_n\ :=\ A+Bn+Cn^2 + D\ 2^n$$
with coefficients $A$, $B$, $C$, $D$ to be determined. Plugging this "Ansatz" into 2) you will get a simple system of linear equations for these coefficients. When you have solved this system the general solution of 2) is given by
$$a_n\ =\ C_1\lambda_1^n +C_2\lambda_2^n+C_3\lambda_3^n+A+Bn+Cn^2 + D\ 2^n\qquad(n\geq 0)$$
A: First problem
Hint:
For the first one, you can use the same trick of the fibonacci numbers.
The characteristic polynomial for this question is:
$$q^3-\frac{3q^2}{2}-q-\frac{1}{4}=0\;.$$
The second Mathematica says:
Solution:
$$\begin{align*}
a(n)&= c_1 \left(2-\sqrt{3}\right)^n+c_2
   \left(2+\sqrt{3}\right)^n+c_3 (-1)^n\\\\
&+\frac{-24 \sqrt{3} \zeta
   \left(-2,\frac{n}{2}\right)+48 \zeta \left(-2,\frac{n}{2}\right)+24
   \sqrt{3} \zeta \left(-2,\frac{n+1}{2}\right)-48 \zeta
   \left(-2,\frac{n+1}{2}\right)}{9 \left(\sqrt{3}-1\right)^3
   \left(1+\sqrt{3}\right)}\\\\
&+\frac{12 \sqrt{3} n^2-24 n^2-30 \sqrt{3} n+60
   n-2^{n+3}+\sqrt{3} 2^{n+2}+27 \sqrt{3}-54}{9 \left(\sqrt{3}-1\right)^3
   \left(1+\sqrt{3}\right)}
\end{align*}$$
A: 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}
$$
