Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Solved it. T(n) = 1 + 1/2 + 1/3 + ... + 1/n for n >= 1. Thanks. – abw333 Oct 1 '12 at 6:27

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.