While working on a recursion problem in CS class, i got to the recursive formula: $$a_0=2, a_n=n+\sum_{i=2}^{n-1}a_i$$ that describes the number of recursive calls for input of size $n\geq2$. It turns out that the numbers in the sequence are known as "Thabit numbers" (see https://en.wikipedia.org/wiki/Thabit_number for more info), and they have a closed form formula: $a_n=3\cdot2^n-1$.
Is there a way the get the closed form out of the recursive form? not a proof by induction, but a way to get from the recursive to the closed form.
Thanks
If $a_n=n+\sum_{i=2}^{n-1}a_i $, then $a_{n+1}=n+1+\sum_{i=2}^{n}a_i $.
Subtracting these, $a_{n+1}-a_n =1+a_n$ or $a_{n+1} =2a_n+1$.
From this you should be able to get $a_n$.
Note that this is a special case of $a_{n} =f_{n}+\sum_{k=1}^{n-1} g_ka_k $. Then $a_{n+1} =f_{n+1}+\sum_{k=1}^n g_ka_k $. Subtracting these, $a_{n+1}-a_n =f_{n+1}-f_{n}+g_na_n $ so that $a_{n+1} =f_{n+1}-f_{n}+(g_n+1)a_n $ which can be readily solves.