Show that the recursive $(g(n) = 2g(n−1) + 1, g(0) = 1)$ is equal to $ g(n) = 2^{n + 1} - 1$ 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$$
 A: 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?
A: 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.$$
A: 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.
A: $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$.
