Recurrence telescoping $T(n) = T(n-1) + 1/n$ and $T(n) = T(n-1) + \log n$

I am trying to solve the following recurrence relations using telescoping. How would I go about doing it?

1. $T(n) = T(n-1) + 1/n$

2. $T(n) = T(n-1) + \log n$

thanks

Solution 1:

In the first case you have $T(n) - T(n-1) = \frac{1}{n}$. If you sum with $n$ going from $2$ to $k$ you get:

$\begin{align*} \big(T(k) - T(k-1)\big) &+ \big(T(k-1) + T((k-2)\big) + \big(T(k-2) + T((k-3)\big) + \cdots + \\ &+ \big(T(4) - T(3)\big) +\big(T(3) - T(2)\big) + \big(T(2) - T(1)\big) = T(k) - T(1) = \sum_{m=2}^k \frac{1}{m}\end{align*}$

Notice how every term except $T(k)$ and $T(1)$ cancels out (I added "backwards" to make this more evident). This is the telescoping part. Then we get $T(n) = T(1) - 1 + H_n $, where $H_n$ is the $n$-th harmonic number $\displaystyle \sum_{m=1}^n \frac{1}{m}$ (I substracted $1$ because the first term $\displaystyle \frac{1}{1}$ doesn't appear in $\displaystyle \sum_{m=2}^n \frac{1}{m}$).

Likewise, in the second case you get: $\displaystyle T(n) = T(1) + \sum_{m=2}^n \log m = T(1) + \sum_{m=1}^n \log m$ (this last equality is given by $\log 1 = 0$; it doesn't make any difference but to me it looks nicer). Or you can use Cameron's hint: $T(n) = T(1) + \log n!$, by applying the product rule for logarithms.

The exact solution depends on the value of $T(1)$ in both cases.

Solution 2:

Hint: a recurrence of the form $T(n) = T(n-1) + f(n)$ will have solutions $T(n) = C + \sum_{k=1}^n f(k)$.