Show that the recursive $(g(n) = 2g(n−1) + 1, g(0) = 1)$ is equal to $ g(n) = 2^{n + 1} - 1$

Question

How do I show that the recursive definition below is equivalent to the explicit one?

$$g(n) = 2g(n−1) + 1, g(0)=1$$

$$g(n) = 2^{n + 1} - 1$$

Answer 1

Hint

$$g(n)=2g(n-1)+1\to g(n)+1=2[g(n-1)+1]$$

Now call $p(n)=g(n)+1$ and you get

$$p(n)=2p(n-1)$$

which is a geometric sequence. Can you finish?

Answer 2

By back substitution for the recurrence relation:

$$g(n)=2g(n-1)+1$$ $$g(n-1)=2g(n-2)+1$$ $$g(n-2)=2g(n-3)+1$$ $$\cdot\cdot\cdot$$ $$g(1)=2g(0)+1=2+1=3$$

So we have $$g(n)=2g(n-1)+1=2[2g(n-2)+1]+1$$ $$=2^2g(n-2)+2+1$$ $$=2^2[2g(n-3)+1]+2+1$$ $$=2^3g(n-3)+2^2+2+1$$ $$=\cdot\cdot\cdot $$ $$=2^{k}g(n-k)+2^{k-1}+2^{k-2}+...+2+1$$ $$=\cdot\cdot\cdot $$ $$=2^{n}g(n-n)+2^{n-1}+2^{n-2}+...+2+1$$ $$=2^{n}g(0)+\sum_{i=0}^{n-1}2^{i}$$ $$=2^{n}+\frac{2^{n}-1}{2-1}$$ $$=2^{n+1}-1.$$

Answer 3

At the beginning let's check the initial condition. We have $g(n)=2^{n+1}-1$. We ought to have $g(0)=1$. Indeed $$g(0)=2^1-1=2-1=1.$$ Additionaly let's check if $g(n)=2g(n-1)+1$. Immediately we obtain

$LHS=2^{n+1}-1$,

$RHS=2\cdot (2^{n}-1)+1=2^{n+1}-2+1=2^{n+1}-1$.

So $LHS=RHS.$

I hope I understood your problem correctly.

Answer 4

$g(n-1) = 2^n -1$ $\Rightarrow$ $(1)$

$2^n -g(n-1) = 1$

This implies $g(n) = 2^{n+1} - [2^n -g(n-1)]$ $g(n) = 2^n [2 -1] + g(n-1)$

From $1$: $g(n) = [g(n-1) +1] [2-1] + g(n-1) $.

And then $g(n) = 2g(n-1) +1$.