# Problem 3. (3 points)

The sequence is defined by the formula $x_{n+3}=2 x_{n+2}+x_{n+1}-2 x_{n}$. Additionally, it is known that $x_{0}=0$, $x_{2}=1$. Find $x_{100}$
Answer: $\frac{4^{50}-1}{3}=422550200076076467165567735125$.

## Solution:

From the recurrence relation, we get that $x_{n+3}-x_{n+1}=2\left(x_{n+2}-x_{n}\right)$. Given that $x_{2}-x_{0}=$ 1, we obtain $x_{n+2}-x_{n}=2^{n}$. Therefore, $x_{100}=\left(x_{100}-x_{98}\right)+\left(x_{98}-x_{96}\right)+\ldots+\left(x_{2}-x_{0}\right)+x_{0}=$ $2^{98}+2^{96}+\ldots+1=4^{49}+4^{48}+\ldots+1==\frac{4^{50}-1}{4-1}=\frac{4^{50}-1}{3}$.