How to solve recurrence relations - expected value

Question

I'm solving a question where the recurrence relation I created is as follows:

$$\begin{cases}E_0=0\\E_1=2\\E_n = 2E_{n-1} + 2&\text{for }n>1\end{cases}$$

How can I create a closed form solution for this?

Answer 1

Write

$$E_n+2=2E_{n-1}+4=2(E_{n-1}+2).$$

As the terms are each time doubled, it should be obvious that the solution is

$$E_n+2=2^n(E_0+2)$$

$$E_n=2^{n+1}-2.$$

Answer 2

This is an arithmetico-geometric sequence and has the solution $$a_n=2(2^n-1)$$

Answer 3

Another approach: difference equations.

1. Get rid of the constant, set $F_{n+1} = E_{n+1} - E_n = \Delta E_{n+1}$: $$ E_{n+1} = 2 E_{n} + 1\\ E_{n} = 2E_{n-1} + 1\\ F_{n+1} = 2F_n $$
2. Write down the recurrence until you arrive at $F_1$. $$ F_{n+1} = 2^{n}F_1 = 2^{n+1} $$

3. Telescopic summation on LHS and RHS: $$ E_{n+1} = 2^{n+1} + 2^{n} + \ldots 2 = 2^{n+2} - 2 = 2(2^{n+1}-1) $$