Question about the particular part in a non homogeneous recurrence

Question

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

Answer 1

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*}$

Answer 2

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.