# Solve the recurrence $T(n)=T(n-1)+\frac{1}{n}$

Assume this recurrence: $$T(n)=T(n-1)+\frac{1}{n}$$

As we can use Master Theorem and Akra-Bazzi method here, I tried to draw a recurrence tree and I reached the whole cost of this tree is $$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n}$$. What's a tight upper and lower bound for this recurrence (I'm talking about $$\Theta$$, not $$\mathcal{O}$$)? Is it even possible to find a $$\Theta$$ for it?

The quantity $$H_n = \sum_{i=1}^n \frac{1}{i}$$ is known as the $$n$$-th harmonic number. It is well-known that $$H_n = \Theta(\log n)$$.

To see this notice that the function $$\frac{1}{x}$$ is monotonically decreasing, which means that the area under $$\frac{1}{x}$$ in the range $$i \le x \le i+1$$ is at most $$\frac{1}{i}$$ (i.e. the area of a rectangle of width $$i+1 - i = 1$$ and height $$\frac{1}{i}$$). In formulas: $$\int_{i}^{i+1} \frac{1}{x} \text{d}x \le \int_{i}^{i+1} \frac{1}{i} \text{d}x = \frac{1}{i}$$.

$$H_n = \sum_{i=1}^n \frac{1}{i} \ge \sum_{i=1}^n \int_{i}^{i+1} \frac{1}{x} \text{d}x = \int_{1}^{n+1} \frac{1}{x} \text{d}x = \ln (n+1) = \Omega( \log n).$$

Similarly, the area under $$\frac{1}{x}$$ in the range $$i \le x \le i+1$$ is at least $$\frac{1}{i+1}$$, i.e., $$\int_{i}^{i+1} \frac{1}{x} \text{d}x \ge \int_{i}^{i+1} \frac{1}{i+1} \text{d}x = \frac{1}{i+1}$$.

$$H_n = 1 + \sum_{i=1}^{n-1} \frac{1}{i+1} \le 1 + \sum_{i=1}^{n-1} \int_{i}^{i+1} \frac{1}{x} \text{d}x = 1 + \int_{1}^{n} \frac{1}{x} \text{d}x=1+\ln n = O(\log n).$$

• Thanks. Can you please write or link a proof to it? Nov 14, 2023 at 14:50
• In the last line, is it $O(n)$ or $O(\log{n})$? Nov 14, 2023 at 15:08
• @IlkayBurak, clearly it is $O( \log n)$. Thanks for pointing out the typo :) Nov 14, 2023 at 15:12