Linear Recursion with backtracking

Question

I have been trying to solve this question for hours. But can't seen to figure out how to solve it by backtracking. Is my current step correct? May I get some help how to continue and derive the simplified solution. thanks!

Question: \begin{align} a_{n} &= a_{n-1}+n ,\\ a_{0} &= 1 \end{align}

My attempt: \begin{align} a_{n}&=a_{n-1}+n\\ &= a_{n-2}+(n-1)+n\\ &= a_{n-2}+2n-1\\ &= a_{n-3}+(n-2)+2n-1\\ &= a_{n-3}+3n-1-2\\ &= a_{n-4}+(n-3)+3n-1-2\\ &= a_{n-4}+4n-1-2-3\\ &= a_{n-5}+(n-4)+4n-1-2-3\\ &= a_{n-5}+5n-1-2-3-4\\ &...\\ &...\\ \end{align}

Edited: Hi All, Thanks for your help. But I need to do it using backtracking.

Answer 1

$\sum_{i=1}^{n}a_i-a_{i-1}=a_n-a_0=\sum_{i=1}^{n}i=\frac{n(n+1)}{2}$

$\therefore a_n=a_0+\frac{n(n+1)}{2}$

Answer 2

Since $a_n$ is linear, every non-leaf node in its recursion tree has out-degree one. Therefore,

$$ a_n ~=~ 1 + \sum_{i = 1}^n i ~=~ 1 + \frac{n(n + 1)}{2} $$