How to solve this recursion which is not homogenous

Question

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

Answer 1

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}. $$

Answer 2

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).$$

Answer 3

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).$$