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$$

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.$$
