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.
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.
Observe that
$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.