recurrence relation question

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.

Answer 1

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.

Answer 2

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.