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

This question already has an answer here:

\begin{align} T(0) & = 0 \\ T(n) & = T(n-1) + \dfrac{1}{n} \end{align} solve the recurrence relation

My work so far:

\begin{align} T(1) & = 1 \\ T(2) & = 1 + \dfrac{1}{2} \\ T(3) & = 1 + \dfrac{1}{2} + \dfrac{1}{3} \\ &\vdots \end{align}

this is the harmonic series, which diverges.

What is the solution to the recurrence relation?

share|cite|improve this question

marked as duplicate by Famous Blue Raincoat, Brian Fitzpatrick, Lord_Farin, quid, Arctic Char Feb 21 '15 at 22:49

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

The actual recurrence relation is the first line of the question. If this is the whole problem, you’re probably expected to prove by induction that $T(n)=H_n$, the $n$-th harmonic number, for $n\ge 1$. – Brian M. Scott Dec 30 '12 at 11:20

The harmonic series diverges when you take the sum to infinity, but this is just the sum to n, which can be calculated. What I'm basically saying is that I think the harmonic series is the right approach.

share|cite|improve this answer

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