Solve recurrence: $T_n =\frac{1}{n}(T_{n-1} + T_{n - 2} + T_{n - 3} + \dots + T_2 + T_1 + T_0) + 1$ with $T_0 = 0$

Solve recurrence:

$T_n =\frac{1}{n}(T_{n-1} + T_{n - 2} + T_{n - 3} + \dots + T_2 + T_1 + T_0) + 1$ with $T_0 = 0$.

The recurrence is defined only on nonnegative integers. Thanks.

-
Solved it. T(n) = 1 + 1/2 + 1/3 + ... + 1/n for n >= 1. Thanks. – abw333 Oct 1 '12 at 6:27

$$nT(n)=T(n-1)+T(n-2)+\ldots+T(1)+T(0)+n\;,$$ so
\begin{align*} T(n+1)&=\frac1{n+1}\Big(T(n)+T(n-1)+\ldots+T(1)+T(0)\Big)+1\\ &=\frac1{n+1}\Big(T(n)+nT(n)-n\Big)+1\\ &=T(n)+\frac1{n+1}\;. \end{align*}
From this you should be able to write $T(n)$ as a very simple summation; you won’t get a nice closed form, but you will get a very important standard sequence whose terms have a name. I’ve left the answer spoiler-protected; mouse-over to see it.
$T(n)=H_n$, the $n$-th harmonic number.