# 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

### 7 answers

0
Ashutosh Bhatia (anonymous)

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

Ashutosh Bhatia 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
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
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
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
• Views866 times
• Answers7 answers
• Followers1 follower
Question and answer is powered by AnsPress