Solving Recursions Without Initial Conditions

Question

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.

Answer 1

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.

Answer 2

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.