i need help with this recursive problem: $T(n) = nT(n-1) + 1$, $T(0) = 0$.

Question

Now here I solved everything but I’m now stuck at the general form how am I gonna write the general form with the (pi) product summation ? Hint there’s something related also with combination and permutation rules in statistics and factorials too but I can’t figure it out.

Answer 1

$$\text{T}(n) = n\text{T}(n-1)+1$$ $$\text{T}(n) = n(n-1)\text{T}(n-2)+n+1$$ $$\text{T}(n) = n(n-1)(n-3)\text{T}(n-3)+n(n-1)+n+1$$

therfore :

$$\text{T}(n) = n(n-1)(n-2)...\text{T}(0)+n(n-1)(n-2)...1+n(n-1)(n-2)...2+n(n-1)(n-2)...3+...+n+1=n!\sum_{k=0}^{n}\frac{1}{k!}$$

Answer 2

Mostafa's answer is correct. However, note that

$$\sum_{k=0}^{n}\frac{1}{k!} = \frac{\lfloor n!e \rfloor}{n!} $$

So the expression simplifies to $$ \text{T}(n) = n!\sum_{k=0}^{n}\frac{1}{k!} $$

\begin{align*} \text{T}(n) &= n!\sum_{k=0}^{n}\frac{1}{k!} \\ &= n! \frac{\lfloor n!e \rfloor}{n!} \\ &= \lfloor n!e \rfloor \end{align*} That is, $T(n)$ is equal to the whole part of $n!e$.

To prove the identity I used above note that $$n!\,e= n! \sum_{k=0}^\infty\frac{1}{k!}=\sum_{k=0}^\infty\frac{n!}{k!}=\sum_{k=0}^n\frac{n!}{k!}+\sum_{k=n+1}^\infty\frac{n!}{k!} \quad (*)$$ Now, note that $$\begin{align} \sum_{k=n+1}^\infty\frac{n!}{k!} &=\frac{1}{n+1}+\frac{1}{(n+1)(n+2)}+\cdots\\ &<\frac{1}{n+1}+\frac{1}{(n+1)(n+1)}+\cdots\\ &=\sum_{k=1}^\infty\frac{1}{(n+1)^k} = \frac{1}{n}\\ \implies \sum_{k=n+1}^\infty\frac{n!}{k!} & < \frac{1}{n} \end{align}$$ Therefore, the second term in ($*$) is always less than one. On the other hand, the first term in ($*$) is always an integer since $k\leq n$ so the identity follows.