<s>[INST] Find the recurrence solution of this relation How would we find the solution of the recurrence relation: $a_n = 2a_{n−1} + 3 · 2^n$ ?
After trying it, I've found it to be $a_n = 2^{n-1} (c_1 + 6n)$
Not sure if this is right..
Thanks!
 [/INST] One very simple technique is available, since this is a first-order recurrence. Unwind it:
$$\begin{align*}
a_n&=2a_{n-1}+3\cdot2^n\\
&=2(2a_{n-2}+3\cdot2^{n-1})+3\cdot2^n\\
&=2^2a_{n-2}+2\cdot3\cdot2^n\\
&=2^2(2a_{n-3}+3\cdot2^{n-2})+2\cdot3\cdot2^n\\
&=2^3a_{n-3}+3\cdot3\cdot2^n\\
&\;\vdots\\
&=2^ka_{n-k}+k(3\cdot2^n)&&\text{conjecture}\\
&\;\vdots\\
&=2^na_0+n(3\cdot2^n)\\
&=(a_0+3n)2^n
\end{align*}$$
Now prove by induction that $a_n=(a_0+3n)2^n$ really is a solution to the recurrence: if $a_n=(a_0+3n)2^n$, then
$$\begin{align*}
a_{n+1}&=2a_n+3\cdot2^{n+1}\\
&=2(a_0+3n)2^n+3\cdot2^{n+1}\\
&=(a_0+3n+3)2^{n+1}\\
&=\big(a_0+3(n+1)\big)2^{n+1}\;,
\end{align*}$$
exactly as desired.
</s>