why$2 (-1 + 2^{1 + n})$ is the answer to the recurrence relation $a_{n}=2a_{n-1}+2$?

Question

$a_{0}=2$

$a_{1}=2(2)+2$

$a_{2}=2(2(2)+2)+2$

$a_{3}=2(2(2(2)+2)+2)+2$

$a_{4}=2(2(2(2(2)+2)+2)+2)+2$

$a_{5}=2(2(2(2(2(2)+2)+2)+2)+2)+2$

To simplifiy

$a_{6}=2^{6}+2^{5}...2^{1}$

so my answer is

$a_{n}=2^{n+1}+2^{n}+...2^{1}$

The correct answer is $2 (-1 + 2^{1 + n})$

How do I make this transition?

Answer 1

Your expression for $a_n$ is correct. So $$a_n=2+\cdots+2^n+2^{n+1}.$$ Now note that this is a sum of $n+1$ terms in geometric progression with first term $a=2$ and the common ratio $r=2$. The sum $S$ can be found by $$S=\frac{a(r^{n+1}-1)}{r-1}$$ So substituting $a=2$ and $r=2$ we get $$a_n=\frac{2(2^{n+1}-1)}{2-1}=2(2^{n+1}-1)$$ as required.

Answer 2

It's equivalent to

$a_{n} + 2 = 2\left(a_{n - 1} + 2\right) = 2^{2}\left(a_{n - 2} + 2\right) = \cdots = 2^{n}\left(a_{0} + 2\right) = 4 \times 2^{n}\implies \bbox[10px,border:1px dotted navy]{\displaystyle a_{n} = 2\left(\,2^{n + 1} - 1\right)} $

Answer 3

If you divide both sides by $2^n$, you will get :

$$\forall k\ge1,\,\frac{a_k}{2^k}-\frac{a_{k-1}}{2^{k-1}}=\frac1{2^{k-1}}$$

Now, cancellation occurs when summing up ($k$ from $1$ to $n$) :

$$\frac{a_n}{2^n}-a_0=\sum_{k=1}^n\frac1{2^{k-1}}=\frac{1-\frac1{2^n}}{1-\frac12}=2-\frac1{2^{n-1}}$$

that is :

$$a_n=2^n\left(4-\frac1{2^{n-1}}\right)=2^{n+2}-2$$

and finally :

$$a_n=2\left(2^{n+1}-1\right)$$

Answer 4

You can also do this in base 2 fairly easily:

$$ \begin{align*} a_0 &= 10_2 \\ a_1 &= 2a_0 + 2 = 100_2 + 10_2 = 110_2 \\ a_2 &= 1100_2 + 10_2 = 1110_2. \end{align*} $$

We can see that by induction we will have. $$a_n = \underbrace{11\cdots1}_{n+1}0_2 = 2(\underbrace{11\cdots1_2}_{n+1}).$$ Now note that $$\underbrace{11\cdots1_2}_{n+1} + 1 = 1\underbrace{00\cdots0_2}_{n+1} = 2^{n + 1}.$$ Therefore $$a_n = 2(2^{n + 1} - 1).$$

Answer 5

The inhomogeneous recurrence relation $$ a_n = 2 a_{n-1} + 2 $$ can be turned into a homogeneous recurrence $$ a_n - a_{n-1} = 2 a_{n-1} + 2 - (2 a_{n-2} + 2) = 2 a_{n-1} - 2 a_{n-2} \iff \\ a_n = 3 a_{n-1} - 2 a_{n-2} $$ and solved by the usual algorithm.

The characteristic polynomial is $$ p(t) = t^2 - 3 t + 2 $$ with roots $r_1 = 1$ and $r_2 = 2$.

So the solution is $$ a_n = k_1 r_1^n + k_2 r_2^n = k_1 + k_2 2^n $$ The initial elements give $$ a_0 = k_1 + k_2 = 2 \\ a_1 = k_1 + 2 k_2 = 6 $$ This gives $k_2 = 4$ and $k_1 = -2$. The solution is $$ a_n = -2 + 4 \cdot 2^n = 2^{n+2} - 2 $$

Answer 6

Let $a_n=2^nb_n$. Then $$ a_{n}=2a_{n-1}+2\\\Downarrow\\2^nb_n=2^nb_{n-1}+2\\\Downarrow\\b_n=b_{n-1}+2^{1-n} $$ Therefore, $$ \begin{align} b_n &=b_0+\sum_{k=0}^{n-1}2^{-k}\\ &=b_0+\frac{1-2^{-n}}{1-2^{-1}}\\[9pt] &=b_0+2-2^{1-n} \end{align} $$ and $$ 2^{-n}a_n=a_0+2-2^{1-n}\\ \Downarrow\\ \begin{align} a_n &=2^na_0+2^{n+1}-2\\[9pt] &=2^{n+2}-2 \end{align} $$