How to solve the recurrence relation $a_n - 2 a_{n-1} = 3 \times 2^n, a_0 = 1$ How to solve the recurrence relation $a_n - 2 a_{n-1} = 3 \times 2^n, a_0 = 1$. By looking at the terms of the relation, it can be seen that it is linear in nature but it is not homogeneous. How to solve such a recurrence relation?
 A: Hint: let $\,a_n=2^n b_n\,$, then $\,2^n b_n - 2 \cdot 2^{n-1} b_{n-1} = 3 \cdot 2^{n} \iff b_n - b_{n-1}=3\,$, so $b_n$ is an arithmetic progression, with common difference $\,3\,$ and $\,b_0=a_0 / 2^0 = 1\,$.
A: Considering the corresponding homogenous recurrence, a general solution for it is $a_n=A\cdot 2^n$. Since the inhomogeneous term resembles the homogeneous solution, we try adding a term of the form $B\cdot n\cdot 2^n$.
Taking $a_n=A\cdot 2^n + B\cdot n\cdot 2^n$, together with $a_0=1, a_1=8$, we obtain
$$A=1\\
2A+2B=8$$
So our general term is $a_n=2^n+3n2^n$, or $a_n=(3n+1)2^n$.
A: Hint
The first thing I would have is to set $a_n=2^n b_n$ which makes
$$a_n - 2 a_{n-1} = 3 \times 2^n\implies b_n-b_{n-1}=3$$ which looks to be simple.
A: Here is a more general approach that will allow you to solve a variety of such problems. Consider that
$$
f_n-2f_{n-1}=3\cdot2^n\\
f_{n-1}-2f_{n-2}=\frac{3\cdot2^n}{2}
$$
Subtract twice the second equation from the first to eliminate the $2^n$ terms to get
$$f_n=4f_{n-1}-4f_{n-2},\quad f_0=1,f_1=8$$
This is a generalized Fibonacci sequence, $f_n=af_{n-1}+bf_{n-2}$ with $f(0)=f_0 \ \&\  f(1)=f_1$. It can be solved with the methods described previously by me here. The general solution is
$$f_n=\left(f_1-\frac{af_0}{2}\right) \frac{\alpha^n-\beta^n}{\alpha-\beta}+\frac{f_0}{2} (\alpha^n+\beta^n) $$
where $\alpha,\beta=(a\pm\sqrt{a^2+4b})/2$.
In the present case, we have $\alpha=\beta$ and the solution takes the form
$$
{{f}_{n}}=\left( {{f}_{1}}-\tfrac{a\,{{f}_{0}}}{2} \right)\,n{{\alpha }^{n-1}}+\tfrac{a{{f}_{0}}}{2}\,{{\alpha }^{n-1}}=\left[ n{{f}_{1}}-(n-1)\tfrac{a{{f}_{0}}}{2} \right]\,{{\alpha }^{n-1}}
$$
Substituting the parameters for the case at hand, we arrive at
$$a_n=(3n+1)2^n$$
This result has been verified numerically.
A: $$a_n=3\cdot2^n+2a_{n-1}$$
$$=3\cdot2^n+2(3\cdot2^{n-1}+2a_{n-2})$$
$$=3\cdot2^n(1+1)+2^{1+1}a_{n-2}$$
$$=3\cdot2^nr+2^ra_{n-r}$$ for $0\le r\le n$
A: Hint:
Let $a_m=am2^m+b_m$
$$3\cdot2^n=a_n-2a_{n-1}=an2^n+b_n-2\{a(n-1)2^{n-1}+b_{n-1}\}=a2^n+b_n-2_{n-1}$$
Set $a=3$ to find $b_n-2_{n-1}=0$
