Question

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

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

Answer 1

`a_n = 2^n -1`

Explanation:

We are given the following information:

`a_n = 2a_(n-1) + 1, a_0 = 0`

We will now evaluate values for n =1, 2, 3, 4, 5 and so on.

By forward substitution method:

`a_1 = 2a_0 + 1 = 0 + 1 = 1\\a_2 = 2a_1 + 1 = 2(1) + 1 =3\\a_3 = 2a_2 + 1 = 2(3) + 1 = 7\\a_4 = 2a_3 + 1 = 2(7) + 1 = 15\\a_5 = 2a_4 + 1 = 2(15) + 1 =31`

If we continue in this manner, we can see a general trend and we can say that

`a_n = 2^n -1`

This is the solution for given recurrence relation.