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

Answer:

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

Step-by-step 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)$