Harmonic numbers are not integers [Solution]

The problem was to show that

$$H_n = \sum_{k=1}^{n} \frac{1}{k} = 1 + \frac{1}{2} + \dots + \frac{1}{n}$$

is never an integer for $n \gt 1$.

Solution

---

There are multiple solutions. One of them uses Bertrand's postulate, which says that there is a prime between $n$ and $2n$ for any $n \gt 1$.

Now consider the largest prime $p$ in $1, 2, \dots, n$.

The denominator of $H_n$ is divisible by $p$. The numerator has terms divisible by $p$, plus the term $1 \times 2 \times \dots \times (p-1) \times (p+1) \times \dots \times n$

By Bertrand's postulate, we have that $2p \gt n$ (otherwise $p$ won't be the largest prime).

Thus the numerator is not divisible by $p$. Thus $H_n$ is not an integer.

Number of AVL trees

AVL trees were one of the first balanced tree structures to provide $O(\log n)$ operations and do so based on height differences between left and right subtree. Look at the wiki link for an exact definition.

Can you give an algorithm to compute the number of AVL trees having exactly $n$ nodes?

[Solution]

Harmonic numbers are not integers

A classic:

Show that

$$H_n = \sum_{k=1}^{n} \frac{1}{k}$$

is never an integer, for $n \gt 1$.

i.e.

$$1 + \frac{1}{2} + \dots + \frac{1}{n}$$

is never an integer for $n \gt 1$.