Question about the particular part in a non homogeneous recurrence Question about the particular part in the following non homogeneous recurrence :
$$a_n - 6a_{n-1} + 9a_{n-2} =  n * 3^n $$
I have the following particual part : $$ a_n = n * 3^n$$
Now the solution of the homogenous part is $$x_1 = 3, x_2 = 3$$ and is of the form $$a_n = (An * B)* 3^n$$
What im struggling with is understanding how this helps me solve for the particual part. The solution to the particual part is: $$ a_n = (Cn^3 + Dn^2) * 3^n$$ how i got to it was $$n^2 * (Cn + D) * 3^n$$ now the part i dont understand is why is there $$(Cn + D)$$ and not just  $ Cn  * 3^n$
Edited 
 A: OK, now with the full recurrence. For the homogeneous part $a_{n + 2} - 6 a_{n + 1} + 9 a_n = 0$ we have a characteristic equation $r^2 - 6 r + 9 = 0$, which is just $(r - 3)^2 = 0$. You have two equal roots, so the solution to the homogeneous part is $a_n^h = (c_1 n + c_2) \cdot 3^n$.
The forcing function is $n \cdot 3^n$, for which the guess of a particular part would ordinarily be $(A n + B) \cdot 3^n$. But this is a solution to the homogeneous recurrence, you have to go up to two more (one for the $3^n$, one for the factor $n$), i.e., guess $a_n^p = (A n^3 + B n^2) \cdot 3^n$ (lower terms are part of the homogeneous solution, they would cancel out). Substitute in your recurrence:
$\begin{align*}
   (A (n + 2)^3 + B (n + 2)^2) \cdot 3^{n + 2}
     - 6 (A (n + 1)^3 + B (n + 1)^2) \cdot 3^{n + 1}
     + 9 (A n^3 + B n^2) \cdot 3^n
     &= (54 A n + 54 A + 18 B) \cdot 3^n
\end{align*}$
Comparing to your recurrence you see:
$\begin{align*}
  54 A
    &= 1 \\
  54 A + 18 B
    &= 0
\end{align*}$
so $A = 1/54, B = - 1/18$. The full general solution is:
$\begin{align*}
   a_n
     &= a_n^h + a_n^p \\
     &= \left(\frac{n^3}{54} - \frac{n^2}{18} + c_1 n + c_2\right) \cdot 3^n 
\end{align*}$
A: Another, general, take is using generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the recurrence by $z^n$, sum over $n \ge 0$ and recognize some sums:
$\begin{align*}
   \sum_{n \ge 0} a_{n + 2} z^n
     - 6 \sum_{n \ge 0} a_{n + 1} z^n
     + 9 \sum_{n \ge 0} a_n z^n
     &= \sum_{n \ge 0} n \cdot 3^n z^n \\
   \frac{A(z) - a_0 - a_1 z}{z^2}
    - 6 \frac{A(z) - a_0}{z}
    + 9 A(z)
    &= z \frac{d}{d z} \frac{1}{1 - 3 z} \\
    &= \frac{3 z}{(1 - 3 z)^2}
\end{align*}$
Solve for $A(z)$:
$\begin{align*}
   A(z)
     &= \frac{(9 a_1 - 54 a_0 + 3) z^3 - (6 a1 - 45 a_0) z^2 + (a_1 - 12 a_0) z + a_0}
             {(1 - 3 z)^4}
\end{align*}$
You want the coefficient of $z^n$. Use the generalized binomial theorem:
$\begin{align*}
   (1 + u)^{-m}
     &= \sum_{n \ge 0} \binom{-m}{n} u^n \\
     &= \sum_{n \ge 0} (-1)^n \binom{n + m - 1}{m - 1} u^n
\end{align*}$
This gives:
$\begin{align*}
  [z^n] A(z)
    &= \left(
         (9 a_1 - 54 a_0 + 3) [z^{n - 3}]
           - (6 a1 - 45 a_0) [z^{n - 2}]
           + (a_1 - 12 a_0) [z^{n - 1}]
           + a_0 [z^n]
       \right) (1 - 3 z)^{-4} \\
    &= \left(
          (9 a_1 - 54 a_0 + 3) \binom{n - 3 + 4 - 1}{4 - 1}
            - (6 a1 - 45 a_0) \binom{n - 2 + 4 - 1}{4 - 1}
            + (a_1 - 12 a_0) \binom{n - 1 + 4 - 1}{4 - 1}
            + a_0 \binom{n + 4 - 1}{4 - 1}
       \right) \cdot 3^n
\end{align*}$
Now the binomial coefficient $\binom{n}{m}$ is a polynomial of degree $m$ in $n$, expanding those you get the full solution.
