Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
Solved it. T(n) = 1 + 1/2 + 1/3 + ... + 1/n for n >= 1. Thanks. –  abw333 Oct 1 '12 at 6:27

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.