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

**T(n) = (n+1)*H**_{n} - n

Now H_{n}≈logn+γ

where γ is the Euler-Mascheroni constant.

**T(n) = O(nlogn)**