Solve the recurrence equation $T\left(n\right)\:=\:n\:+\:\sum _{i=1}^{n-1}\left(T\left(i\right)\right)$

Question

I am trying to find the runtime of:

$T\left(n\right)\:=\:n\:+\:\sum _{i=1}^{n-1}\left(T\left(i\right)\right)$

$T(1)= 1$

What is the way to solve this kind of problems?

Answer 1

Hint.

$$ \cases{ T_n = n +\sum_{i=1}^{n-1}T_i\\ T_{n-1} = n-1 + \sum_{i=1}^{n-2}T_i } $$

subtracting the second from the firts we have

$$ T_n-T_{n-1}=1+T_{n-1} $$

or

$$ T_n -2T_{n-1}= 1 $$

with solution (it is easy to solve)

$$ T_n = c_02^n+2^n-1 $$

and considering the initial value

$$ T_n = 2^n-1 $$