# Problem 3. (3 points)

The sequence $\left\{a_{n}\right\}$ is defined by the conditions $a_{1}=0 \quad$ and $a_{n+1}=\sum_{k=1}^{n}\left(a_{k}+1\right)$ for $n \geqslant 1$. Find the explicit formula for this sequence.

Answer: $a_{n}=2^{n-1}-1$
Solution:

By subtracting the formulas for $a_{n+1}$ and $a_{n}$ from each other, we get $a_{n+1}-a_{n}=a_{n}+1$, that is, $a_{n+1}=2 a_{n}+1$ for $n>1$.

Now let's prove the formula $a_{n}=2^{n-1}-1$ by induction. The base case is $n=1$ and indeed, $a_{1}=0=2^{0}-1$.

Next, we will use the obtained recurrence formula and verify that if $a_{n}=$ $2^{n-1}-1$, then $a_{n+1}=2\left(2^{n-1}-1\right)+1=2^{n}-1$.