<s>[INST] 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
 [/INST] 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).$$
</s>