Please refer to the images to see the example.
I do not understand how substituting a_n = (2^n) − 1 into the recurrence relation
a_n+1 =a_0 +···+a_n +n+1=(2^0 −1)+···+(2^n −1)+n+1
results in the sum 1+2+4+···+2^n = 2^(n+1) −1.
I see that the partial sums to 1 + 2 + 4 + ... coincide with the terms in the recurrence relation, but I do not understand how one goes from substituting a_n into each term of the recurrence relation a_n+1 to deriving the "explicit formula for n+1". I hope someone can help me bridge this gap in my understanding.
Thanks.
By a direct derivation : \begin{align*} \sum_{k=0}^{n} (2^{k}-1) + n+1 &= \sum_{k=0}^{n} 2^{k} -(n+1) + n+1\\ &= \sum_{k=0}^{n} 2^{k} \end{align*}
Now this is a standard geometric sum but let's compute it anyway \begin{align*} S_n &= \sum_{k=0}^{n} 2^{k}\\ &= 1 + \sum_{k=1}^{n+1} 2^{k} - 2^{n+1}\\ &= 1 + 2 \sum_{k=0}^{n} 2^{k} - 2^{n+1}\\ &= 2 S_n + 1 - 2^{n+1} \end{align*} Solving for $S_n$ gives $S_n=2^{n+1}-1$ as desired.