Question

Use the backward substitution method to obtain the closed form formula for the recurrence relation

an= 2an-1 + 1, and a0 =0.

Answer 1

`a_0=0; \; a_n=2^n-1 \; (n>0)`

Explanation:

`a_0=0`

`a_1=2a_0+1=1`

`a_2=2a_1+1=3=1+2`

`a_3=2a_2+1=7=1+2+4`

`a_4=2a_3+1=15=1+2+4+8`

`a_5=2a_4+1=31=1+2+4+8+16`

So, we can infer that

`a_n=1+2^1+2^2+2^3+...+2^(n-1)`

and we only need to find out a formula for this sum (a geometric reason with common ratio 2)

Let's call

`S=1+2^1+2^2+...2^(n-1)`

then,

`2S=2+2^2+...2^(n-1)+2^n`

hence,

`S-2S=1-2^n`

`2S-S=S=2^n-1`

and we have our closed formula for the sequence

`a_0=0; \; a_n=2^n-1 \; (n>0)`