+1 vote
219 views
Express $T(n)$ in terms of the harmonic number $H_{n}= \sum_{t=1}^{n} 1/i, n \geq 1$, where $T(n)$ satisfies the recurrence relation,

$T(n)=\frac{n+1}{n} T(n - 1)+1$, for $n \geq \sum$ and $T(1) = 1$

What is the asymptotic behaviour of $T(n)$ as a function of $n$ ?
edited | 219 views

the n-th harmonic number is the sum of the reciprocals of the first n natural numbers.

https://en.wikipedia.org/wiki/Harmonic_number

And Using Back-Substitution it can be found out that $T(n) = O(n^n)$

Hope it Helps!

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