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?

Plenty of methods for this sort of equation; see here for instance. — user170231, Jun 16 '20 at 20:00

score 0 · Answer 1 · 2020-06-16T20:10:29.023

0

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.$$

edited Jun 16 '20 at 20:10

answered Jun 16 '20 at 20:04

score 0 · Answer 2 · answered Jun 16 '20 at 20:04

0

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

answered Jun 16 '20 at 20:04

K.defaoite

Though I'm not sure what expected value has to do with this. – K.defaoite Jun 16 '20 at 20:05
The question definitely lacks that context but e.g. recurrence relations often yield expected hitting times of states in Markov chain theory. – Nap D. Lover Jun 16 '20 at 20:08

score 0 · Answer 3 · answered Jun 16 '20 at 20:31

Another approach: difference equations.

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 $$
Write down the recurrence until you arrive at $F_1$. $$ F_{n+1} = 2^{n}F_1 = 2^{n+1} $$

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) $$

3 Answers3