2

I have the following recurrence relation: $$a_n = 2a_{n-1} + 2^n; a_0 = 0$$ I used the characteristic equation method and some method I found online by calculating the $n+1$ th term and subtracting accordingly the equation with $a_{n+1}$ minus the equation with $a_{n}$: $$a_{n+1} = 2a_n + 2^{n+1} \\ a_{n+1} - 2a_n = 2a_n - 4a_{n-1} + 2^{n+1}- 2^{n+1} \\ a_{n+1} - 4a_n + 4a_{n-1} = 0$$ Using $x^n$ as a solution: $$x^{n-2}(x^2 - 4x+4) = 0$$ I obtained the multiple solution $x= 2$. So we have that: $$a_n = 2^n A_1 + n 2^n A_2$$

How do I finish?

mandella
  • 1,852
  • 2
    Shortcut: $$\frac{a_n}{2^n}=\frac{a_{n-1}}{2^{n-1}}+1\qquad\frac{a_0}{2^0}=0$$ – Did Apr 07 '17 at 19:29

3 Answers3

2

Hint: let $a_n = 2^n b_n\,$, then the recurrence reduces to $b_n=b_{n-1}+1\,$.

dxiv
  • 76,497
1

You can't use the characteristic equation methoded beacuse it is not a linear recurrence but you can use the generating function method, let $f(x)=\sum_{n=0}^\infty a_nx^n$ : $$f(x)=\sum_{n=0}^\infty a_nx^n=0+\sum_{n=1}^\infty a_nx^n=\sum_{n=1}^\infty (2a_{n-1}+2^n)x^n\\=2x\sum_{n=0}^\infty a_nx^n+\sum_{n=1}^\infty (2x)^n=2xf(x)+\sum_{n=1}^\infty (2x)^n$$ Thus $\forall x\in(-\frac{1}{2},\frac{1}{2})$ we have : $$(1-2x)f(x)=\sum_{n=1}^\infty (2x)^n=2x\sum_{n=0}^\infty (2x)^n=\frac{2x}{1-2x}$$ So : $$f(x)=\frac{2x}{(1-2x)^2}=\sum_{n=0}^\infty 2^nnx^n$$ Finally : $$\forall n\in \mathbb{N}, a_n= 2^nn$$

Bérénice
  • 9,367
1

Given: $a_n = 2a_{n-1} + 2^n; a_0 = 0$ and you can find $a_n = 2^n A_1 + n \cdot 2^n A_2$. Now we have to find $A_1$ and $A_2$.

We put $n=1$ in $a_n = 2a_{n-1} + 2^n$. So $a_1 = 2a_0 + 2^1=2$.

Now, let's put $n=0$ and $n=1$ in $a_n = 2^n A_1 + n\cdot 2^n A_2$. Hence

$2^0 A_1 + 0\cdot 2^0 A_2 = 0 \implies A_1 =0$

$ 2^1 A_1 + 1\cdot 2^1 A_2 = 2 \implies A_2 = 1$

Therefore we find that $a_n=n\cdot2^{n}$.

scarface
  • 1,933