TITLE: How to solve the recurrence relation $a_n - 2 a_{n-1} = 3 \times 2^n, a_0 = 1$
QUESTION [2 upvotes]: 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?

REPLY [1 votes]: 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.
{"set_name": "stack_exchange", "score": 2, "question_id": 2408394}