# Problem 3. (3 points)

The sequence $\left\{a_{n}\right\}$ is defined by the conditions $a_{1}=-1$ 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-2}-1$ for $a>1, a_{1}=-1$

Solution:

By subtracting the formula for $a_{n}$ from that for $a_{n+1}$, 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-2}-1$ by induction. The base case is $n=2$, and indeed, $a_{2}=a_{1}+1=0=2^{0}-1$.

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