Solving Recursions Without Initial Conditions I am trying to solve the following recursion but it does not appear that I can use characteristic equations or generating functions since I do not have initial conditions.  Is there another way I am missing or can I assume initial conditions to use the above methods?
$$a_n = 3a_{n-1} -2a_{n-2} + 2^n + n^2$$
For example, if I found roots x = -1 and x = -2 I could then write the general solution as $α(−1)^n+β(−2)^n + P(n)$ for some particular solution? How would I get this particular solution? I am rusty at undetermined coefficients.
 A: The set of solutions is a two-dimensional (affine) space. Once you have found any particular solution $(a_n)$, adding any solution of $d_n=3d_{n-1}-2d_{n-2}$ will produce another solution $(a_n+d_n)$.
As for example arbitrary values for  $d_0,d_1$ can be chosen, we obtain a two-parameter set of solutions.
Any method of your choice should work; if necessary, add initial conditions $a_0=\alpha, a_1=\beta$ at will.
A: A general way of solving such, as expounded in Wilf's "generatingfunctionology":
$$
a_{n + 2} = 3 a_{n + 1} - 2 a_n + 4 \cdot 2^n + (n + 2)^2
$$
Define the ordinary generating function:
$$
A(z) = \sum_{n \ge 0} a_n z^n
$$
By the properties of generating functions, with the operator $D = \dfrac{d}{d z}$:
$$
\frac{A(z) - a_0 - a_1 z}{z^2}
  = 3 \frac{A(z) - a_0}{z} - 2 A(z) + 4 \frac{1}{1 - 2 z} 
      + (z D + 2)^2 \frac{1}{1 - z}
$$
Solving this, written as partial fractions:
$$
A(z) = \frac{5 - a_0 + a_1}{1 - 2 z} 
         + \frac{2}{(1 - 2 z)^2}
         + \frac{2 a_0 - a_ 1 - 1}{1 - z}
         - \frac{3}{(1 - z)^2}
         - \frac{1}{(1 - z)^3}
         - \frac{2}{(1 - z)^4}
$$
Expanding each of the terms by the binomial theorem, with $\displaystyle \binom{-k}{n} = (-1)^n \binom{k - 1 + n}{k - 1}$:
$$
\begin{align*}
a_n &= (5 - a_0 + a_1) \cdot 2^n
         + 2 \binom{n + 1}{1} \cdot 2^n
         + (2 a_0 - a_1 - 1)
         - 3 \binom{n + 1}{1}
         - \binom{n + 2}{2}
         - 2 \binom{n + 3}{3} \\
    &= \frac{1}{6} ((12 n + 6 a_1 - 6 a_0 + 42) \cdot 2^n
                      - 2 n^3 - 15 n^2 - 49 n
                      - 6 a_1 + 12 a_0 - 42)
\end{align*}
$$
Getting the complete solution this way isn't substantially harder than getting the solution by more traditional methods.
The help of maxima with the algebra is gratefully acknowledged.
