2. The sequence $\left(a_{n}\right)$ is defined by the following relations: $a_{1}=1, a_{2}=3, a_{n}=a_{n-1}-a_{n-2}+n$ (for $n \geqslant 3$). Find $a_{1000}$.
Answer: 1002.

Solution. Let's list the first terms of the sequence:

$$
1,3,5,6,6,6,7,9,11,12,12,12,13,15,17,18,18,18,19,21, \ldots
$$

We can see a pattern: $a_{n+6}=a_{n}+6$. Let's prove it. We have

$a_{n+1}=a_{n}-a_{n-1}+n+1=\left(a_{n-1}-a_{n-2}+n\right)-a_{n-1}+n+1=-a_{n-2}+2 n+1$.

By substituting $n$ with $n+2$ in the obtained equation, we get

$$
a_{n+3}=-a_{n}+2(n+2)+1=-a_{n}+2 n+5 .
$$

Now, let's substitute $n$ with $n+3$:

$$
a_{n+6}=-a_{n+3}+2(n+3)+5=a_{n}-2 n-5+2(n+3)+5=a_{n}+6
$$

Now it's easy to find the answer:

$$
a_{1000}=a_{4+6 \cdot 166}=a_{4}+6 \cdot 166=6+6 \cdot 166=1002
$$

Evaluation. Full solution is worth 12 points. If the pattern is noticed but not proven, then (with the correct answer) 6 points.