It makes no sense to ‘put $a_n=b_n$’ when you have no $b_n$ in the problem. What you wanted is the auxiliary equation $b^2-6b+9=0$, which you correctly solved to find the general solution
$$a_n=(c_1+c_2n)3^n\tag{1}$$
for some constants $c_1$ and $c_2$. You determine those by using the known values of $a_0$ and $a_1$: when $n=0$ equation $(1)$ becomes
$$1=a_0=(c_0+c_2\cdot0)\cdot3^0\;,\tag{2}$$
and when $n=1$ it becomes
$$6=a_1=(c_1+c_2\cdot1)\cdot3^1\;.\tag{3}$$
Now simplify $(2)$ and $(3)$ and solve for $c_1$ and $c_2$ to finish deriving the solution.
To verify it by mathematical induction you must do three things:
- verify that $3^0+0\cdot3^0=a_0$, i.e., that the formula gives the correct value when $n=0$;
- verify that $3^1+1\cdot3^1=a_1$, i.e., that the formula gives the correct value when $n=0$; and
- show that if $n\ge 2$ and $a_k=3^k+k3^k$ for $k=0,1,\ldots,n-1$, then $a_n=3^n+n3^n$.
(1) and (2) are the basis steps of your induction, and (3) is the induction step: in it you’re showing that if the expression $3^k+k3^k$ gives the right value for $a_k$ for all $k<n$, then it also gives the correct value for $a_n$. In carrying out this step you’ll use the recurrence that defines the sequence.
My suggestion is to think of the undetermined coefficient method for linear non-homogeneous ODE, which can be found in any elementary ODE book. Let me illustrate. Let say we want to find a particular solution of
$$
ay''+by'+cy=f(x),
$$
where $a,b,c$ are constants. If $f(x)=x^3$, you will need to plug in a polynomial of degree 3 (try it and see why you need the lower degree terms). Now, if $f(x)=e^{ax}$, then you will need to plug in $y=Ke^{ax}$. I believe it is obvious that you do not need any other terms. Notice that if $f(x)=2^x$, it is a particular case of an exponential since $f(x)=2^x=e^{\ln{(2)} x}$. Now, the only exceptions to those rules if if $f(x)$ is a solution to the homogeneous problem. For example in the case of
$$
y''-y=e^x.
$$
In this case, $y=ke^x$ does not work. You need to pre-multiply by $x$ to try $y=kxe^x$. In general, if $f(x)$ is a solution of the homogeneous problem, you need to pre-multiply the ansatz's I suggested above by $x$. All these results are formulated in theorems in any decent elementary ODE book (for example, the one written by Nagle and Saff). But I think these rules can be understood quite easily by working out simple examples. Note that in relation to your example $n3^n$, I can add the rule that if $f(x)=x^2 e^{ax}$ and that $e^{ax}$ is not a solution of the homogeneous problem, you need to try a polynomial of degree $3$ times $e^{ax}$. Note that if you try to add a term like $x^4e^{ax}$ to your solution, then this term will automatically produce a term proportional to $x^4e^{ax}$, which is unwanted.
If $e^{ax}$ was a solution, then you would need to pre-multiply by $x$. You would try $y=x(bx^3+cx^2+dx+f)e^{ax}$. Again, all this are in the theorems. Now, if $a$ was a double root of the characteristic equation, you would need to pre-multiply by $x^2$ instead.
For example
$$
y''-6y'+9y=x^2e^{3x}.
$$
You would try $y=x^2(ax^2+bx+c)e^{3x}.
$
Note that in the case of $n3^n$ you mention, the characteristic polynomial has a double root $3$, thus the homogeneous problem has $3^n$ and $n3^n$ as solutions, that is why you need to pre-multiply by $n^2$ and try $n^2(an+b)3^n$,
All what I said I believe extends to your difference equations. Your difference equations are ``like'' second order differential equation with inhomogeneities made of exponentials and polynomials. So, the rules for the undetermined coefficient method do extend.
Best Answer
For $a_n^{p_2}$, you have
$$a_n = 6a_{n-1} - 9a_{n-2} + 3^n \tag{1}\label{eq1A}$$
Going to the next value of $n$, you have
$$a_{n+1} = 6a_{n} - 9a_{n-1} + 3^{n+1} \tag{2}\label{eq2A}$$
Next, \eqref{eq2A} minus $3$ times \eqref{eq1A} becomes
$$\begin{equation}\begin{aligned} a_{n+1} - 3a_n & = (6a_{n} - 9a_{n-1} + 3(3^{n})) - 3(6a_{n-1} - 9a_{n-2} + 3^n) \\ a_{n+1} - 3a_n & = 6a_{n} - 27a_{n-1} + 27a_{n-2} \\ a_{n+1} & = 9a_{n} - 27a_{n-1} + 27a_{n-2} \end{aligned}\end{equation}\tag{3}\label{eq3A}$$
This is now a homogenous linear difference equation with a characteristic equation of
$$\lambda^3 - 9\lambda^2 + 27\lambda - 27 = (\lambda - 3)^3 = 0 \tag{4}\label{eq4A}$$
I'll leave it to you to finish the rest.