Find explicit form of following: $a_n=3a_{n-1}+3^{n-1}$ I wanted to find the explicit form of a recurrence relation , but i  stuck in nonhomogenous part.

Find explicit form of following: $a_n=3a_{n-1}+3^{n-1}$ where $a_0=1 , a_1 =4,a_2=15$

My attempt:
For homogeneous part , it is obvious that $c_13^n$
For non-homogenouspart = $3C3^n=9C3^{n-1}+3^n \rightarrow 9C3^n=9C3^{n}+3 \times3^n$ , so there it not solution.
However , answer is $n3^{n-1} + 3^n$ . What am i missing ?
 A: Hint. Divide both sides by $3^n$ we get
$$
\frac{a_n}{3^n}=\frac{a_{n-1}}{3^{n-1}}+\frac{1}{3}
$$
Now we let $b_n=\frac{a_n}{3^n}$, so $b_n=b_{n-1}+\frac{1}{3}$.
A: The homogeneous part has solution in $3^n$ and the RHS part also has $3^n$ so you need to search for a particular solution of the form $(an+b)3^n$.
When you have a root $r$ of the characteristic equation of multiplicity $m$ and if the RHS is $P(n)r^n$ with $P$ polynomial then you need to search for a particular solution of the form $Q(n)r^n$ with $Q$ polynomial and $$\deg(Q)=\deg(P)+m$$
Note that in the case RHS is $P(n)\alpha^n$ with $\alpha$ not a root, then we just say $m=0$.
Here $r=3,\ m=1$ (single root of $r-3=0$) and $P(n)=\frac 13$ is a constant, thus a polynomial of degree $0$, so $Q$ is of degree $1$ or simply $Q(n)=an+b$.
A: Let $A(z)=\sum_{n \ge 0} a_n z^n$ be the ordinary generating function.  The recurrence relation and initial condition imply that
\begin{align}
A(z) 
&= a_0 + \sum_{n \ge 1} a_n z^n \\
&= 1 + \sum_{n \ge 1} (3a_{n-1} + 3^{n-1}) z^n \\
&= 1 + 3z \sum_{n \ge 1} a_{n-1} z^{n-1} + z \sum_{n \ge 1} 3^{n-1} z^{n-1} \\
&= 1 + 3z \sum_{n \ge 0} a_n z^n + z \sum_{n \ge 0} (3z)^n \\
&= 1 + 3z A(z) + \frac{z}{1-3z}.
\end{align}
Solving for $A(z)$ yields
\begin{align}
A(z) 
&= \frac{1+z/(1-3z)}{1-3z} \\
&= \frac{1-2z}{(1-3z)^2} \\
&= \frac{2/3}{1-3z} + \frac{1/3}{(1-3z)^2} \\
&= \frac{2}{3}\sum_{n\ge 0}(3z)^n + \frac{1}{3}\sum_{n\ge 0}\binom{n+1}{1}(3z)^n \\
&= \sum_{n\ge 0}\left(\frac{2}{3}+\frac{1}{3}(n+1)\right)3^n z^n \\
&= \sum_{n\ge 0}(n+3)3^{n-1} z^n.
\end{align}
Hence $a_n=(n+3)3^{n-1}$ for $n \ge 0$.
