Recurrence Relation – T(n)=1+T(n-1)+1/n

0

can any body tell me how to solve the following recurrence relation
T(n)=1 when n=1
T(n)=1+T(n-1)+1/n

by back substitution i will get the series like 1+1/2+1/3+1/4+1/5+………. can anybody tell me how to solve this series

Ravi Garg edited question
    0
    Yash Kumar (anonymous)

    sum of the reciprocals of the positive integers,this is called the harmonic series:1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + … As we add up more and more terms of this series the sum just keep getting larger–larger than any predetermined constant.(So if we add enough terms the sum is larger than 10, larger than 10^10, larger than 10^1000000…).When this happens we say the series diverges.If you have trouble seeing that the harmonic series diverges, think of it this way:1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + … = ( 1/1 ) + ( 1/2 ) + ( 1/3 + 1/4 ) + ( 1/5 + 1/6 + 1/7 + 1/8 ) + … (where each set of parenthesis stops at a reciprocal of a power of two.) Replacing the terms in each set of parenthesis by the smallest term (in those parenthesis) we get a smaller sum:1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + … > ( 1/1 ) + ( 1/2 ) + ( 1/4 + 1/4 ) + ( 1/8 + 1/8 + 1/8 + 1/8 ) + … = 1/1 + 1/2 + 1/2 + 1/2 + 1/2 + … which clearly gets arbitrarily large!

    Yash Kumar answered
      0
      Ashutosh Bhatia (anonymous)

      log n is the good approximation of the above series. Think about the integral from 1 to n of function 1/x.

      Ashutosh Bhatia answered
        0
        Prashant Singh (anonymous)

        as number increasing the value is decreasing …step1 T(n)=1+T(n-1)+1/n………..T(n)= n+T(1)+1/2+1/3+1/4……..1/n……………..hence T(n)= n+(1+1/2+1/3….1/n) =n+c =O(n) because 1+1/2+1/3….1/n is conversing to a constant hence answer is linear O(n).

        Prashant Singh answered
          0
          Ashutosh Bhatia (anonymous)

          I agree with prashant here T(n) = n + logn and therefore O(n)

          Ashutosh Bhatia answered
            0
            Koteswararao Pittala (anonymous)

            is integral 1/x= 1+1/2+1/3+1/4+1/5+………..

            Koteswararao Pittala answered
              Add image to editor add image from link

              Question stats

              • Active
              • Views928 times
              • Answers7 answers
              • Followers1 follower
              Question and answer is powered by AnsPress