# 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!

• We are here to help you find answers. So, what have you tried, and where did you get stuck? – TMM Apr 16 '13 at 23:15
• The above and also: what do you call "solution" to in this case? A formula only involving $\,n\,$ or what? – DonAntonio Apr 16 '13 at 23:25

## 2 Answers

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.

• But this differs from what wolfram says? – tekman22 Apr 17 '13 at 6:26
• @jtm22: What does Wolfram|Alpha give you? – Brian M. Scott Apr 17 '13 at 6:33
• @BrianMScott - wolfram verifys that the solution is $a_n = 2^{n-1} (c_1 + 6n)$ – tekman22 Apr 17 '13 at 7:07
• @jtm22: That really doesn’t help much, since you haven’t said what $c_1$ is. – Brian M. Scott Apr 17 '13 at 7:08
• @BrianMScott I was thinking that $c_1$ is similar to what GlenO was saying? Do you suggest I just disregard their reasoning - wolframalpha.com/input/?i=a%5Bn%5D%3D2*a%5Bn-1%5D%2B3*2%5En ? Thanks – tekman22 Apr 17 '13 at 7:12

Hint: What happens when you try a solution of the form $$a_n = b_n + c\cdot2^n$$ and what value of $c$ simplifies the recurrence relation?

• I've found the solution to be $a_n = 2^{n-1} (c_1 + 6n)$ – tekman22 Apr 16 '13 at 23:41