# recurrence relation question

$$T(0)=1$$ $$(N\gt0)\;T(N)\;=\;\sum_{k=0}^{N-1}(k+1)T(k)$$

How can I find the closed representation of this function? I don't need to know the answer, I just need someone to point me in the right direction.

• Welcome to MSE! In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are; this will prevent people from telling you things you already know, and help them give their answers at the right level. Furthermore, please avoid the use of pictures for critical portions of your post. Pictures cannot be searched and are inaccessible to those using screen readers. – user409521 Apr 3 '17 at 2:52
• For some basic information about writing math on MSE see here, here, here and here. – user409521 Apr 3 '17 at 2:53

## 2 Answers

Since, for $n \ge 1$, $t(n) =\sum_{k=0}^{n-1}(k+1) t(k)$, $t(n+1)-t(n) =(n+1)t(n)$ so $t(n+1) =(n+2)t(n)$ for $n \ge 1$.

Note that $t(1) = 1$.

Therefore, for $n \ge 1$, $\dfrac{t(n+1)}{t(n)} =n+2$ so that

$\begin{array}\\ \dfrac{t(n+1)}{t(1)} &=\prod_{k=1}^{n}\dfrac{t(k+1)}{t(k)}\\ &=\prod_{k=1}^{n}(k+2)\\ &=\prod_{k=3}^{n+2}k\\ &=\frac12(n+2)!\\ \text{or}\\ t(n) &=\frac12(n+1)!\\ \end{array}$

Note:

This came after an attempt to find $f(x) =\sum_{n=0}^{\infty} x^n t(n)$ (coming up with the differential equation $x^2f'+(2x-1)f+(1-x) =0$, which Wolfy said had the solution $f(x) =\dfrac{e^{-1/x}}{x^2} \left(c + Ei(1/x))\right) - \dfrac1{2 x} + \dfrac12$), and then showing that $t(n)$ grew faster that $n^r$ for any $r$ and faster than $a^n$ for any $a$.

This solution was suggested by $\sum_{k=1}^n k k! = (n + 1)! - 1$ and remembering how that was proved.

Start writing out what the sequence is, and see if you can notice a pattern... that's normally a good first step for simple problems.

Think about breaking up the sum on the right into something more convenient.

Then you can find the ratio of consecutive terms, which will give more insight to the closed form solution.