Solve the recurrence relation:

Question

Solve the recurrence relation $$ \cases{T(1) = 1\\T(n) = n+\sum_{i = 1}^{n-1}T(i) & for $n\geq 2$} $$

Answer 1

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

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

So we have $T(1)=1$, $T(2)=3$, $T(3)=7$, $T(4)=15$ etc.

Fromt his you should be able to guess an expression for $T(n)$ and prove it by induction.

Answer 2

It's a bit ad-hoc (@gandalf61's solution is better), but if you write out the terms, you'll see that

$$ T(n) = 1 + (1+2) +(1+2+3) + \ldots (1+ \ldots + n-1) + n $$

In other words, you have 1 term equal to $n$, one to $n-1$, two to $n-2$, etc until $n-1$ terms equal to $1$. So the solution is

$$ T_n = n +\sum_{k=1}^{n-1}k(n-k) $$

which is very easy to find.