$T(n) = \frac{n+1}{n}T(n-1) + 1$ --------------------------------------------------(1)

$T(n-1) = \frac{n}{n-1}T(n-2) + 1$--------------------------------------------(2)

$T(n-2) = \frac{n-1}{n-2}T(n-3) + 1$--------------------------------------------(3)

substituting value of $T(n-1)$ from eqn (2) in eqn (1)

$T(n) = \frac{n+1}{n}*\frac{n}{n-1}T(n-2) + \frac{n+1}{n} + 1$

$T(n) = \frac{n+1}{n-1}T(n-2) + \frac{n+1}{n} + 1$

now substituting value of $T(n-2)$ in above eqn

$T(n) = \frac{n+1}{n-1}* \frac{n-1}{n-2}T(n-3) + \frac{n+1}{n-1} + \frac{n+1}{n} + 1$

$T(n) = \frac{n+1}{n-2}T(n-3) + \frac{n+1}{n-1} + \frac{n+1}{n} + 1$

.

.

.

.

so on

$T(n) = \frac{n+1}{n-k+1}T(n-k) + \frac{n+1}{n} + \frac{n+1}{n-1} + ...... + \frac{n+1}{n-k+2} + 1$

$T(n) = \frac{n+1}{n-k+1}T(n-k) + (n+1)*( \frac{1}{n} + \frac{1}{n-1} +.....+ \frac{1}{n-k+2}) + 1$

now let $n-k=1$ so $k = n-1$, substitute value of $k$ in above eqn

$T(n) = \frac{n+1}{n-(n-1)+1}T(1) + (n+1)*( \frac{1}{n} + \frac{1}{n-1} +.....+ \frac{1}{n-(n-1)+2}) + 1$

$T(n) = \frac{n+1}{2} + (n+1)*( \frac{1}{n} + \frac{1}{n-1} +.....+ \frac{1}{3}) + 1$

$T(n) = \frac{n+1}{2}+ (n+1)*(H_n - \frac{1}{2} - 1) + 1$

$T(n) = \frac{n+1}{2} + (n+1)*H_n - \frac{n+1}{2} - (n+1) + 1$

$\mathbf{T(n) = (n+1)*H_n - n}$

Now $H_n \approx \log n+γ$

where $γ$ is the Euler-Mascheroni constant.

**$\mathbf{T(n) = O(n \log n)}$**