Solve recurrence relation: $T(n) = \frac{n}{n+1}T(n-1) + 1$ I am not able to solve this recurrence relation by substitution and variable change method.
$$T(n) = \frac{n}{n+1}T(n-1) + 1;\ \ T(1) = 1 $$

(n+1)T(n) = nT(n-1) + n+1

Let  
 S(n) = (n+1)T(n)   S(0) = T(0) = c
       S(n) = S(n-1) + n+1   

Since,    S(n-1) = S(n-2) + n
    therefore,   S(n) = S(n-2) + n+1 + n
          for k terms...
S(n) = S(n-k) + (n+1) +n +.....+ (n-k+2)
k = n
 S(n) = S(0) + (n+1) + n + ...+ (n-k+2)
      = c + (n+1) + n + (n-1) + ......+ 2 + 1 - 1
      = (n+1)(n+2)/2  + (c-1)
      = (n^2 + 3n + 2)/2  +  c - 1
      = n^2/2 + 3n/2  + c

S(n) = O(n^2)

from our substitution -
T(n)(n+1) = O(n^2)
T(n)=1/(n+1) O(n^2)
We can neglect +1 in n+1

then,
T(n) = O(n)

