I have come across recurrences like $T(n) = n + \sum_{i=1}^{n-1}{T(i-1)}$ . All I could make out is that they are related to factorials and binomial coefficients and expanding them doesn't seem to lead me anywhere. Also, a reduction for the purpose of finding an asymptotic upper bound to $T(n)$.. like $T(n) \leq n+(n-1)T(n-1)$ don't seem to give a closed form solution.
Is there a way to solve the recurrence in its original or reduced form ? Or any general method for obtaining closed form solutions to these factorial-like recurrences like master theorem etc.?
We can easily get $$T(n+1)=T(n)+T(n-1)+1.$$ If $T(0)=T(1)=1$, we call $\{T(n)\}$ the Leonardo sequence. Now we claim that
PROOF. For $n=0$ and $n=1$, (1) is easily verified.
Now suppose that (1) is true for $0\leqslant k\leqslant n$. Thus \begin{align*} T(n+1)& =T(n)+T(n-1)+1\\ & =(2F_{n+1}-1)+(2F_n-1)+1\\ & =2(F_{n+1}+F_n)-1\\ & =2F_{n+2}-1. \end{align*} Hence (1) holds for $n\in \mathbb{N}$.$\quad\square$
If $T(0)=2a-1,T(1)=2b-1$, (1) is also true, but now $F_n$ satisfies that $$F_1=a,\ F_2=b,\ F_{n+2}=F_{n+1}+F_n.$$ I'm sure that it's enough.