Find the recurrence solution of this relation

Question

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

score 1 · Answer 1 · answered Apr 16 '13 at 23:27

1

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?

answered Apr 16 '13 at 23:27

Glen O

12,425

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

Brian M. Scott · Accepted Answer · 2013-04-19T18:37:07.360

1

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.

edited Apr 19 '13 at 18:37

answered Apr 16 '13 at 23:50

Brian M. Scott

616,228

But this differs from what wolfram says? – tekman22 Apr 17 '13 at 06:26
@jtm22: What does Wolfram|Alpha give you? – Brian M. Scott Apr 17 '13 at 06:33
@BrianMScott - wolfram verifys that the solution is $a_n = 2^{n-1} (c_1 + 6n)$ – tekman22 Apr 17 '13 at 07:07
@jtm22: That really doesn’t help much, since you haven’t said what $c_1$ is. – Brian M. Scott Apr 17 '13 at 07:08
@BrianMScott I was thinking that $c_1$ is similar to what GlenO was saying? Do you suggest I just disregard their reasoning - http://www.wolframalpha.com/input/?i=a%5Bn%5D%3D2a%5Bn-1%5D%2B32%5En ? Thanks – tekman22 Apr 17 '13 at 07:12
@jtm22: Since you didn’t specify any initial value, I suspect that $c_1$ there is an arbitrary constant that depends on the the initial value. Note that if you set $c_1=2a_0$, the W|A closed form reduces to mine. – Brian M. Scott Apr 17 '13 at 07:21
Makes sense Brian, Thanks! – tekman22 Apr 17 '13 at 07:33
@jtm22: You’re welcome! – Brian M. Scott Apr 17 '13 at 07:34
@BrianMScott Are you missing a 3 in this solution? – tekman22 Apr 19 '13 at 18:27
@jtm22: Yes, there was a typo in the very last line, which I’ve now fixed. – Brian M. Scott Apr 19 '13 at 18:37

Find the recurrence solution of this relation

2 Answers2