Solving a recurrence equation with sum

Question

In my algorithm analysis, I have the following recurrence equation:

$T(n) = n \sum_{i=1}^{n}(T(n-i)) + c, T(0) = 1$

I want to solve this equation so that to construct big-O from it. I know that T(n) = T(n-1) belongs to O(2^n), but I don't know how to simplify the sum part. Any hints or steps are much appreciated.

Answer 1

A simplification I see:

$$ T_n = n\sum_{i=0}^{n-1} T_i +c = nT_{n-1} + \frac{n}{n-1} (n-1)\sum_{i=0}^{n-2} T_i +c = nT_{n-1} + \frac{n}{n-1} T_{n-1} +c = \frac{n^2}{n-1} T_{n-1} +c $$ Maybe someone can find an expression $T_n = f(n)$ which would be even better for the sake of complexity

Answer 2

$$ T_n = n\sum_{k=0}^{n-1}T_k+c\\ T_{n-1} = (n-1)\sum_{k=0}^{n-2}T_k+c $$

hence

$$ \frac{T_n}{n}-\frac{T_{n-1}}{(n-1)} = T_{n-1} -\frac{c}{n(n-1)} $$

or

$$ T_n - \left(\frac{n^2}{n-1}\right)T_{n-1}=-\frac{c}{n-1} $$

Which has as general solution

$T_n = C_0 n \frac{\Gamma(n+1)}{\Gamma(2)}+c F(n)$