adamant's blog

By adamant, history, 44 hours ago, In English

Hi everyone!

In this blog, we will learn how to find the asymptotic expansion of $$$H_n = \sum\limits_{k=1}^n \frac{1}{k}$$$.

Motivational example

In the recent Meta Hacker Cup, problem C of the round 3 reduced to finding the sum of $$$\frac{1}{a+bk}$$$ for given $$$a$$$ and $$$b$$$, over all $$$k \in [L, R)$$$.

Now, putting it into Wolfram, you can see that

$$$ \sum\limits_{k=L}^{R-1} \frac{1}{a+bk} = \frac{\psi(\frac{a}{b}+R)-\psi(\frac{a}{b}+L)}{b}, $$$

where $$$\psi(z)$$$ is the digamma function. It is sufficient to solve this problem, as you can use boost or scipy to find it. But I feel like it's long time to satiate my curiosity on how it can be computed without knowing the digamma function in advance, and this blog is focused just on that.

Harmonic numbers

First of all, let's define $$$H(n) = \sum\limits_{k=1}^{n} \frac{1}{k}$$$, the $$$n$$$-th harmonic number. If $$$a = 0$$$, we can say that

$$$ \sum\limits_{k=L}^{R-1} \frac{1}{bk} = \frac{H(R-1)-H(L-1)}{b}. $$$

Notice how it is similar to the formula with the digamma function? That's not a coincidence! In fact, we can e.g. re-define $$$H(n)$$$ as

$$$ H(n) = \sum\limits_{k=0}^{n-1} \frac{1}{n-k}, $$$

and this definition will be quite easy to update to also allow non-integer $$$n$$$, by changing the upper sumation limit to $$$\lfloor n \rfloor - 1$$$.

With this in mind, we can re-express the whole sum as

$$$ \sum\limits_{k=L}^{R-1} \frac{1}{a+bk} = \frac{1}{b} \sum\limits_{k=0}^{R-L} \frac{1}{\frac{a}{b}+(R-k)} = \frac{H(\frac{a}{b}+R-1) - H(\frac{a}{b}+L-1)}{b}. $$$

This is also similar to the formula with $$$\psi$$$, because $$$\psi(n) = H(n-1)-\gamma$$$ for integer $$$n$$$, where $$$\gamma$$$ is the Euler–Mascheroni constant.

Asymptotics of $$$H(n)$$$

As a very rough first estimate, we can approximate

$$$ H(n) = \sum\limits_{k=1}^n \frac{1}{k} \approx \int\limits_1^n \frac{1}{x} dx = \ln n, $$$

which is a quite known estimation in many applications, e.g. when finding all divisors of all numbers up to $$$n$$$.

Now, the approach that we will use to finding the true asymptotic expansion of $$$H(n)$$$ is assuming that $$$H(n) = \ln n + F(\frac{1}{n})$$$, where $$$F(x)$$$ is an analytic function, meaning that it can be expressed as $$$F(x) = a_0 + a_1 x + a_2 x^2 + \dots$$$, i.e. as a power series.

Note: While $$$F(\frac{1}{n})$$$ is a convenient way to represent the expansion, it actually does not converge in any $$$n$$$. The idea here is rather that each prefix sum $$$F_k(x) = a_0 + \dots + a_k x^k$$$ serves as an increasingly better approximation as you put $$$n \to \infty$$$, but also provides worse approximations on smaller $$$n$$$.

Finding the expansion of $$$F(\frac{1}{n})$$$

With this assumption, let's find the coefficients of $$$F(x)$$$. For this, consider

$$$ H(n) - H(n-1) = \ln n - \ln (n-1) + F(\frac{1}{n})-F(\frac{1}{n-1}) = \frac{1}{n} $$$

In this form, we can rewrite the LHS as a power series in $$$\frac{1}{n}$$$. Indeed,

$$$ \ln n - \ln(n-1) = \ln \frac{n}{n-1} = \ln \frac{1}{1-\frac{1}{n}} = \sum\limits_{k=1}^\infty \frac{1}{kn^k}, $$$

as follows from the standard expansion $$$\log \frac{1}{1-x} = \sum\limits_{k=1}^\infty \frac{x^k}{k}$$$. At the same time,

$$$ F(n) - F(n-1) = \sum\limits_{k=1}^\infty a_k \left(\frac{1}{n^k} - \frac{1}{(n-1)^k}\right) $$$

can also be represent as a power series in $$$\frac{1}{n}$$$ as

$$$ \frac{1}{(n-1)^k} = \frac{1}{n^k} \frac{1}{(1-\frac{1}{n})^k} = \frac{1}{n^k} \sum\limits_{t=0}^\infty \binom{k+t-1}{t} \frac{1}{n^t}, $$$

as follows from the standard expansion for $$$\frac{1}{(1-x)^k}$$$. Putting it all back together, we arrive at

$$$ \sum\limits_{k=1}^\infty \frac{1}{n^k}\left[\frac{1}{k}-\sum\limits_{t=1}^{k-1} \binom{k-1}{k-t} a_t\right] = \frac{1}{n} $$$

For $$$k=1$$$, the coefficients near $$$\frac{1}{n^k}$$$ on both sides are already same, and for all higher $$$k$$$ this requirement turns into

$$$ \boxed{\sum\limits_{t=1}^{k-1} \binom{k-1}{k-t} a_t = \frac{1}{k}} $$$

Using the identity above for $$$k=2,3,\dots$$$ allows us to find $$$a_1 = \frac{1}{2}$$$, $$$a_2 = -\frac{1}{12}$$$, $$$a_3=0$$$, $$$a_4=\frac{1}{120}$$$, and so on. Okay but what about $$$a_0$$$? Well, actually, $$$a_0=\gamma$$$! But it is not important for our purposes at all, because it cancels out when we subtract $$$H(L-1)$$$ from $$$H(R-1)$$$.

Relation to Riemann zeta function

One can also derive the same result in the form

$$$ H(n) = \ln n + \gamma + \frac{1}{2n} + \sum\limits_{k=2}^{\infty} \frac{\zeta(1-k)}{n^k}, $$$

where $$$\zeta(x)$$$ is the Riemann zeta-function that already occurred e.g. here, but I fail to give any meaningful interpretation to this fact.

One highly "illegal" way to interpret this is as follows. We previously said it makes sense to define

$$$ H(n) = \sum\limits_{k=0}^{n-1} \frac{1}{n-k} $$$

But we can rewrite it as

$$$ H(n) = \frac{1}{n} \sum\limits_{k=0}^{n-1} \frac{1}{1-\frac{k}{n}} = \frac{1}{n}\sum\limits_{k=0}^{n-1} \sum\limits_{t=0}^\infty \frac{k^t}{n^t} = \sum\limits_{t=0}^{\infty} \frac{1}{n^{t+1}} \sum\limits_{k=0}^{n-1} k^t $$$

Now, we already know that $$$\sum\limits_{k=1}^{\infty} k^t = \zeta(-t)$$$, so at $$$n \to \infty$$$ we get

$$$ H(n) \approx \frac{1}{2n} + \sum\limits_{t=2}^\infty \frac{\zeta(1-t)}{n^t}, $$$

except that what we did was very illegal, and hence it missed the $$$\ln n + \gamma$$$ part completely. But as always with Riemann's zeta function, it quite surprisingly allows us to get estimations for stuff that is actually analytic quite precisely.

Afterthoughts

Are there any simpler ways to derive it?

  • Vote: I like it
  • +92
  • Vote: I do not like it

»
44 hours ago, # |
  Vote: I like it -8 Vote: I do not like it

Very interesting stuff. I always thought it was $$$\log(n)$$$ because that is what it usually is in tutorials.

  • »
    »
    42 hours ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    is it?

    • »
      »
      »
      42 hours ago, # ^ |
        Vote: I like it -9 Vote: I do not like it
      Spoiler
»
44 hours ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Okay, now the "funny" way to connect $$$H(n)$$$ with Riemann's zeta function (also putting it in the blog body).

We previously said it makes sense to define

$$$ H(n) = \sum\limits_{k=0}^{n-1} \frac{1}{n-k} $$$

But we can rewrite it as

$$$ H(n) = \frac{1}{n} \sum\limits_{k=0}^{n-1} \frac{1}{1-\frac{k}{n}} = \frac{1}{n}\sum\limits_{k=0}^{n-1} \sum\limits_{t=0}^\infty \frac{k^t}{n^t} = \sum\limits_{t=0}^{\infty} \frac{1}{n^{t+1}} \sum\limits_{k=0}^{n-1} k^t $$$

Now, we already know that $$$\sum\limits_{k=0}^{\infty} k^t = \zeta(-t)$$$, unless $$$t=0$$$, so at $$$n \to \infty$$$ we get

$$$ H(n) \approx \frac{1}{2n} + \sum\limits_{t=2}^\infty \frac{\zeta(1-t)}{n^t}, $$$

except that what we did was very illegal, and hence it missed the $$$\ln n + \gamma$$$ part completely. But as always with Riemann's zeta function, it quite surprisingly allows us to get estimations for stuff that is actually analytic quite precisely.

»
43 hours ago, # |
  Vote: I like it -10 Vote: I do not like it

bashkort how can i read and understand these things?