# 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
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.

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!

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).

0
Ashutosh Bhatia (anonymous)

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

0
Koteswararao Pittala (anonymous)

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