How to solve this recursion which is not homogenous I have the following recursion
$$a_n = \frac{1}{4}a_{n-1}+\frac{1}{4}(\frac{2}{3})^{n-1}$$
I've tried first to solve the homogeneous equation (shifting by one)
$$(E - \frac{1}{4})a_n = 0$$
where $Ea_n = a_{n+1}$ is the shift operator. The only solution to this equation is $E=\frac{1}{4}$. Now I thought that for a non-homogeneous equation, where the term $d(n)$ does not depend on the underlying recursion has the form $d(n) = k\mu^n$ and $\mu$ is not a root of the homogeneous equation, the solution is given by
$$a_n = \frac{k\mu^n}{\Phi(\mu)}$$
where $\Phi$ is the characteristic equation of the homogeneous one. In my case $d(n) = \frac{1}{4}\frac{2}{3}^{n}$, so $k=\frac{1}{4}$ and $\mu = \frac{2}{3}$. Thus the solution should be given by
$$a_n = \frac{\frac{1}{4}\frac{2}{3}^n}{\frac{2}{3}-\frac{1}{4}}=\frac{\frac{1}{4}\frac{2}{3}^n}{\frac{5}{12}}=\frac{3}{5}\frac{2}{3}^n$$
However, the solution should be $$\frac{3}{5}\frac{2}{3}^n-\frac{3}{5}\frac{1}{4}^n$$. What did I wrong?
Note: the question arises from another problem, see here
 A: Note that $$4^na_n-4^{n-1}a_{n-1}=\left(\dfrac{8}{3}\right)^{n-1}$$ now telescope.
Add: Let me compete the computation to get a closed form. After taking the summation $$4^na_n-a_0=\sum_{k=1}^n\left(\dfrac{8}{3}\right)^{k-1}=\dfrac{1-\left(\dfrac{8}{3}\right)^{n}}{1-\left(\dfrac{8}{3}\right)}$$ and hence $$4^na_n=a_0+\dfrac{3}{5}\left(\left(\dfrac{8}{3}\right)^n-1\right).$$
A: The telescoping summation helps: $$a_n=\frac{1}{4}a_{n-1}+\frac{1}{4}\left(\frac{2}{3}\right)^{n-1},$$
$$\frac{1}{4}a_{n-1}=\frac{1}{4^2}a_{n-2}+\frac{1}{4^2}\left(\frac{2}{3}\right)^{n-2},$$
$$\frac{1}{4^2}a_{n-2}=\frac{1}{4^3}a_{n-3}+\frac{1}{4^3}\left(\frac{2}{3}\right)^{n-3},$$
$$\cdot$$
$$\cdot$$
$$\cdot$$
$$\frac{1}{4^{n-2}}a_2=\frac{1}{4^{n-1}}a_1+\frac{1}{4^{n-1}}\left(\frac{2}{3}\right)^{1}.$$
Id est, $$a_n=\frac{1}{4^{n-1}}a_1+\frac{1}{4}\left(\frac{2}{3}\right)^{n-1}+...+\frac{1}{4^{n-1}}\left(\frac{2}{3}\right)^{1}=$$
$$=\frac{1}{4^{n-1}}a_1+\frac{\frac{1}{4}\left(\frac{2}{3}\right)^{n-1}\left(\left(\frac{3}{8}\right)^{n-1}-1\right)}{\frac{3}{8}-1}=\frac{a_1}{4^{n-1}}+\frac{2}{5}\left(\left(\frac{2}{3}\right)^{n-1}-\left(\frac{1}{4}\right)^{n-1}\right).$$
A: The recurrent equation is
\begin{align}
a_n-\dfrac{1}{4}a_{n-1}=\dfrac{1}{4}\left(\dfrac{2}{3}\right)^{n-1}, n=1,2,\ldots.
\end{align}
Solve the homogeneous equation,
$$a_n-\dfrac{1}{4}a_{n-1}=0.$$
The characteristic equation is
$$r-\dfrac{1}{4}=0$$
which gives
$$r=\dfrac{1}{4}.$$
The solution of homogeneous equation is
$$a_n^{(c)}=C\left(\dfrac{1}{4}\right)^n.$$
Now, we solve non-homogenous equation.
Let the particular solution is
$$a_n^{(p)}=A\left(\dfrac{2}{3}\right)^{n-1}.$$
Substituting particular solution to recurrent equation gives
\begin{align}
A\left(\dfrac{2}{3}\right)^{n-1}-\dfrac{1}{4}A\left(\dfrac{2}{3}\right)^{n-2}=\dfrac{1}{4}\left(\dfrac{2}{3}\right)^{n-1}, n=1,2,\ldots.
\end{align}
Now, we have
\begin{alignat}{2}
&&
A\left(\dfrac{2}{3}\right)^{n-1}-\dfrac{3}{8}A\left(\dfrac{2}{3}\right)^{n-1}&=\dfrac{1}{4}\left(\dfrac{2}{3}\right)^{n-1}, n=1,2,\ldots.\\
\iff\quad 
&&
\dfrac{5}{8}A\left(\dfrac{2}{3}\right)^{n-1}&=\dfrac{1}{4}\left(\dfrac{2}{3}\right)^{n-1}, n=1,2,\ldots.
\end{alignat}
Now we have
\begin{alignat}{2}
&&
\dfrac{5}{8}A&=\dfrac{1}{4}\\
\iff\quad
&&
A&=\dfrac{2}{5}.
\end{alignat}
So, the particular solution is
$$a_n^{(p)}=\dfrac{2}{5}\left(\dfrac{2}{3}\right)^{n-1}.$$
So, the solution of recurrent equation is
\begin{alignat}{2}
&&
a_n&=a_n^{(c)}+a_n^{(p)}\\
\iff\quad
&&
a_n&=C\left(\dfrac{1}{4}\right)^n+\dfrac{2}{5}\left(\dfrac{2}{3}\right)^{n-1}\\
\iff\quad
&&
a_n&=C\left(\dfrac{1}{4}\right)^n+\dfrac{3}{5}\left(\dfrac{2}{3}\right)^{n}.
\end{alignat}
Related to this question: Markov chain probability state question,
the initial condition is $a_1=\dfrac{1}{4}$.
We find constant $C$ as below
\begin{alignat}{2}
&&
a_n&=C\left(\dfrac{1}{4}\right)^n+\dfrac{3}{5}\left(\dfrac{2}{3}\right)^{n}\\
\iff\quad
&&
a_1&=C\left(\dfrac{1}{4}\right)+\dfrac{3}{5}\left(\dfrac{2}{3}\right)=\dfrac{1}{4}
\\
\iff\quad
&&
\dfrac{1}{4}C&=\dfrac{1}{4}-\dfrac{2}{5}=-\dfrac{3}{20}\\
\iff\quad
&&
C&=-\dfrac{3}{5}
\end{alignat}
So, the solution is
$$
a_n=-\dfrac{3}{5}\left(\dfrac{1}{4}\right)^n+\dfrac{3}{5}\left(\dfrac{2}{3}\right)^{n}.
$$
