Please help us to find the general solution of this recurrence: $x_{n+1}=5^{n-1} x_n+3^n$ Please help us to find the general solution of this recurrence:
$$x_{n+1}=5^{n-1} x_n+3^n.$$
We found the solution for the associated homogeneous recurrence
$x_{n+1}=5^{n-1} x_n$
which is 
$$x_n =  5^{(n-1)(n-2)/2}x_1,$$
and we tried to use it to find a particular solution of the nonhomogeneous recurrence, but unfortunately we were not able to find it.
 A: (Nothing original here.)
If
$x_{n+1}
=u_{n+1} x_n+v_{n+1}
$,
let
$U_n
=\prod_{k=1}^n u_k
$
so
$\dfrac{U_n}{u_n}
=\prod_{k=1}^{n-1} u_k
=U_{n-1}
$.
Then
$\dfrac{x_{n+1}}{U_{n+1}}
=\dfrac{u_{n+1}}{U_{n+1}} x_n+\dfrac{v_{n+1}}{U_{n+1}}
=\dfrac{x_{n}}{U_{n}}+\dfrac{v_{n+1}}{U_{n+1}}
$.
Letting
$a_n
=\dfrac{x_{n}}{U_{n}}
$
and
$b_n
=\dfrac{v_{n}}{U_{n}}
$,
this becomes
$a_{n+1}
=a_n+b_{n+1}
$.
Therefore
$a_{n+1}-a_n
=b_{n+1}
$.
Summing
$a_n-a_1
=\sum_{k=1}^{n-1}(a_{k+1}-a_k)
=\sum_{k=1}^{n-1}b_{k+1}
$
so
$a_n
=a_1+\sum_{k=1}^{n-1}b_{k+1}
=a_1+\sum_{k=2}^{n}b_{k}
$.
Replacing these
by their definitions,
$\dfrac{x_{n}}{U_{n}}
=\dfrac{x_{1}}{U_{1}}+\sum_{k=2}^{n}\dfrac{v_{k}}{U_{k}}
$
so
$x_{n}
=\dfrac{x_{1}U_n}{U_{1}}+\sum_{k=2}^{n}\dfrac{U_nv_{k}}{U_{k}}
=x_{1}\prod_{k=1}^n u_k+\sum_{k=1}^{n-1}v_k\prod_{j=k+1}^n u_j
$.
Put in
$u_n = 5^{n-2},
v_n=3^{n-1}
$
and see what you get.
You probably ought 
to check my math,
also.
A: This is the route I usually take but....
$$\begin{align}
x_{n+1}&=5^{n-1} x_n+3^n \\
&=5^{n-1}(5^{n-2} x_{n-1}+3^{n-1})+3^n \\
&\quad = 5^{2n-(1+2)}x_{n-1}+(3 \cdot 5)^{n-1} +3^n \\
&=5^{2n-(1+2)}(5^{n-3}x_{n-2}+3^{n-2})+(3\cdot5)^{n-1}+3^n \\
&\quad =5^{3n-(1+2+3)}x_{n-2}+5^{2n-(1+2)}3^{n-2}+5^{n-1}3^{n-1}+3^n \\
&\vdots \\
&\vdots \quad \text{seeing a pattern...after i steps} \\
&\vdots \\
&=5^{(i+1)n+\frac{(i+1)(i+2)}{2}}x_{n-i}+\sum_{k=0} ^{i} 5^{kn-\frac{k(k+1)}{2}}3^{n-k} \\
&\vdots \\
&\vdots \quad \text{supposing that you do it n times, and set i=n...} \\
\\
&\vdots \\
&=5^{\frac{(n+1)(3n+2)}{2}}x_0+\sum_{k=0} ^{n} 5^{kn-\frac{k(k+1)}{2}}3^{n-k} \\
\end{align}$$
I'm not sure if this is any help to you but I couldn't resist taking a stab.
