Solve recurrence relation: $T(n) = \frac{n}{n+1}T(n-1) + 1$

Question

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 $$

Answer 1

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

Answer 2

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} $$

Answer 3

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

Answer 4

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