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 $$
 A: This is a linear difference equation so
$$
T(n)=T_h(n)+T_p(n)
$$
where
$$
T_h(n)-\frac{n}{n+1}T_h(n-1) = 0\\
T_p(n)-\frac{n}{n+1}T_p(n-1) = 1\\
$$
For the homogeneous solution is is clear that making
$$
T_h(n) = \frac{C_0}{n+1}
$$
we have the solution. Now for the particular making $T_p(n)=  \frac{C_0(n)}{n+1}$ we have that
$$
C_0(n)-C_0(n-1)=n+1
$$
hence
$$
C_0(n) = \frac 12(n+1)(n+2)
$$
and finally
$$
T(n) = \frac{C_0}{n+1}+\frac{n+2}{2}
$$
A: evaluating a few terms you can find a pattern:
$T_1=1=\frac 2 2, T_2=\frac{5}{3}, T_3=\frac{9}{4}, T(4)=\frac {14} 5, \ldots$
Namely the pattern is that the numerator of the nth term is the sum of the first (n+1) terms diminished by 1.  This can be found most easily by noticing the difference in the numerator between successive terms.  The denominator is simply the (n+1)th term.  We can then prove it by mathematical induction:
$$T_n=\frac{\left(\sum_{i=1} ^ {n+1} i\right) -1}{n+1}= \cdots =\frac{n+2}{2}-\frac 1 {n+1}$$
Proof:
Base case: $n=1$ implies $T_1=\frac 3 2 - \frac 1 2 =1$ .  Good so far.
Inductive step:  Does our $T_n \implies T_{n+1} $?   Letting $n\to n+1 $ in the original definition, we multiply our $T_n$ by $\frac {n+1} {n+2}$ and add $1$, as this is what is defined by our formula with the index increased by 1....so do we get
$$T_{n+1}=\frac{n+3}{2}-\frac {1}{n+2}$$ ??  
We do..
A: Let $$S_n=(n+1)T_n$$
Then
$$S_n=S_{n-1}+n+1$$
So
$$S_n=\sum_{k=3}^n k +S_1$$
You should be able to continue and compute $S_n$ and therefore $T_n$.
A: (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)

