EDIT: I have now expanded my original comment to an answer which follows below the horizontal line.
Our analysis shall rest on these inequalities
$$
0 < \log \left(\frac{2n+1}{2n+\frac{1}{2}} \right) < \log(2) - a_n \leq \log \left( \frac{2n+2}{2n+1} \right).
$$
We begin by estimating
$a_n$ from above. By definition, we have
$$
a_n = \sum_{j=n+1}^{2n} \frac{1}{j}
$$
We recognize that
$a_n$ as the composite midpoint rule for the integral
$$
I = \int_{n+\frac{1}{2}}^{2n+\frac{1}{2}} \frac{1}{x}dx = \log\left(\frac{2n+\frac{1}{2}}{n + \frac{1}{2}} \right)
$$
corresponding to the uniform step size
$h=1$. The composite midpoint rule
$I_h$ is useful in this situation, because if
$f \in C^2([a,b])$, then there is at least one
$\xi \in [a,b]$ such that
$$
\int_a^b f(x) dx - I_h = \frac{1}{24}(b-a) h^2 f''(\xi).
$$
In our case,
$M_h = a_{n}$ and
$f(x) = \frac{1}{x}$. We do not know the exact value of
$\xi$, but we have
$f'(x) = -x^{-2}$ and
$f''(x) = 2x^{-3}$. We can therefore conclude that
$$
I - a_n = \frac{1}{24}(b-a) h^2 f''(\xi) > 0.
$$
It follows that
$$
a_n < I = \log\left(\frac{2n+\frac{1}{2}}{n + \frac{1}{2}} \right).
$$
We shall now estimate
$a_n$ from below. We have
$$
a_n = \sum_{j=n+1}^{2n} \frac{1}{j} > \sum_{j=n+1}^{2n} \int_j^{j+1} \frac{1}{x}dx = \int_{n+1}^{2n+1} \frac{1}{x} dx = \log\left( \frac{2n+1}{n+1} \right).
$$
In summary, we have established that
$$
\log\left( \frac{2n+1}{n+1} \right) < a_n < \log\left(\frac{2n+\frac{1}{2}}{n + \frac{1}{2}} \right)
$$
It follows immediately that
$$
\log(2) - \log\left(\frac{2n+\frac{1}{2}}{n + \frac{1}{2}} \right) < \log(2) - a_n < \log(2) - \log\left( \frac{2n+1}{n+1} \right)
$$
or equivalently
$$
\log \left( \frac{2n+1}{2n+\frac{1}{2}} \right) < \log(2) - a_n < \log\left(\frac{2n+2}{2n+1} \right)
$$
We now take a moment to consider the fact that while the inequalities give us rather tight control over
$\log(2)-a_n$, they are perhaps not the easiest expressions to manipulate. We shall now derive expressions that will allows us to determine the order of convergence. We shall consider the right hand side first. We shall write
$$
\frac{2n+2}{2n+1} = 1 + \frac{1}{2n+1}
$$
Let
$g(x) = \log(1+x)$. Then
$g'(x) = \frac{1}{1+x}$ and
$$
\frac{\log(1+x)}{x} = \frac{g(x)}{x} = \frac{g(x) - g(0)}{x-0} \rightarrow g'(0) = 1
$$
simply because
$g$ is differentiable at
$x=0$. We conclude that
$$
\frac{\log\left(\frac{2n+2}{2n+1} \right)}{ \frac{1}{2n+1}} \rightarrow 1, \quad n \rightarrow \infty, \quad n \in \mathbb{N}.
$$
In particular, there exists
$N_1 > 0$ such that
$$
\log\left(\frac{2n+2}{2n+1} \right) \leq 2 \left( \frac{1}{2n+1} \right)
$$
for all
$n \ge N_1$. We shall now apply the same technique to the left hand side. We have
$$
\frac{2n+1}{2n+\frac{1}{2}} = 1 + \frac{\frac{1}{2}}{2n+\frac{1}{2}}
$$
and we can now conclude that
$$
\frac{\log\left( \frac{2n+1}{2n+\frac{1}{2}} \right) }{\frac{\frac{1}{2}}{2n+\frac{1}{2}} } \rightarrow 1, \quad n \rightarrow \infty, \quad n \in \mathbb{N}
$$
In particular, there exists
$N_2>0$ such that
$$
\log\left( \frac{2n+1}{2n+\frac{1}{2}} \right) \ge \frac{1}{2} \left( \frac{\frac{1}{2}}{2n+\frac{1}{2}} \right)
$$
for all
$n \ge N_2$. We now return to the task of squeezing
$a_n$ against
$\log(2)$. If we choose
$N = \max\{N_1, N_2\}$ then
$$
\frac{1}{2} \left( \frac{\frac{1}{2}}{2n+\frac{1}{2}} \right) \leq \log(2) - a_n \leq 2 \left( \frac{1}{2n+1} \right)
$$
for all
$n \ge N$.
We observe that we have
$\log(2) - a_n$ squeezes by two sequence that both tend to zero. How fast do they converge? Consider the right-hand sequence which is given by
$$
x_n = \frac{2}{2n+1}
$$
It is straightforward to verify that
$$
\frac{x_{n+1}}{x_n} = \frac{2n+1}{2n+3} \rightarrow 1, \quad n \rightarrow \infty, \quad n \in \mathbb{N}
$$
Clearly, we have
$q = 1$ and
$\mu = 1$ for this sequence. This shows that
$x_n$ tends to zero and the order of convergence is sublinear. Here the critical point is that
$\mu = 1$ and not
$\mu \in [0,1)$ which is what is required for linear convergence. It is straight forward to verify that the left-hand sequence which is given by
$$
y_n = \frac{\frac{1}{4}}{2n+\frac{1}{2}}
$$
converges sublinearly to zero. In short, the sequence
$\log(2) - a_n$ has no choice but to converge to sublinearly to zero.
There are certain key points to notice here. The definition of order of convergence is not easy to dance with and plucking
$q$ and
$\mu$ out of thin air is essentially impossible. What we have to do is to recognize the fact that we need information about the behavior of
$a_n$, i.e., good upper and lower bounds. One bound was easy because it hinged on the definition of the logarithm. The second bound was harder and I had to browse through a list of rules, before I found a rule where the error term had the appropriate sign. In the end, I did not apply the definition directly to the sequence in question, but squeezed it between two sequences of with the same order of convergence.
OP's problem is exceedingly relevant for everybody who does floating point arithmetic. The key observation is that
$a_{n}$ tends to
$\log(2)$ as
$n$ tends to infinity. This can be use to demonstrate the strength of different subroutines for computing sums. We can sum the terms in decreasing order, increasing order, using tree wise summation or Kahan summation. Eventually all routines will disobey the mathematical reality, but bad routines will do so for much smaller values of
$n$ than good routines.
The original comment follows below the next horizontal line:
Note: **This is *not* an answer**, but a comment that is too long for the standard format and offers some insight as to why the convergence is so slow.
Let
$$H_n = \sum_{j=1}^n \frac{1}{j}$$ denote the
$n$th partial sum of the harmonic series. Then
$$a_n = H_{2n} - H_{n}.$$
We shall now investigate the general case of
$H_m - H_n$ where
$m \ge n$. It is straightforward to verify that
$$ \int_j^{j+1} \frac{1}{x} dx \leq \frac{1}{j} \leq \int_{j-1}^j \frac{1}{x}dx.$$
To show this we use that the function
$x \rightarrow \frac{1}{x}$ is continuous and monotone decreasing on the interval
$(0,\infty)$.
It follows that
$$H_m - H_n = \sum_{j=n+1}^m \frac{1}{j} \leq \int_n^m \frac{1}{x} dx = \log\left(\frac{m}{n}\right).$$
We also have
$$ H_m - H_n = \sum_{j=n+1}^m \frac{1}{j} \ge \int_{n+1}^{m+1} \frac{1}{x}dx = \log \left( \frac{m+1}{n+1} \right). $$
We conclude that
$$ \log\left( \frac{m+1}{n+1} \right) \leq H_m - H_n \leq \log\left(\frac{m}{n}\right).$$
In the case of
$m=2n$ we find that
$$ \log\left( \frac{2n+1}{n+1} \right) \leq a_n \leq \log(2)$$
or equivalently
$$ 0 \leq \log(2) - a_n \leq \log(2) - \log\left(\frac{2n+1}{n+1} \right)$$
At this point we have confirmed that
$a_n \rightarrow \log(2)$. It is clear that
$$\log\left(\frac{2n+1}{n+1}\right) = \log\left(2 \frac{n+\frac{1}{2}}{n+1} \right) = \log(2) + \log \left( \frac{1 + \frac{1}{2n}}{1 + \frac{1}{n}}\right)$$ and
$$0 \leq \log(2) - a_n \leq \log\left( \frac{1 + \frac{1}{n}}{1 + \frac{1}{2n}} \right) \approx \frac{1}{2n}$$
where the last approximation is based on the Taylor expansion
$$\log(1+x) = x + O(x^2), \quad x \rightarrow 0, \quad x \not = 0.$$
Objectively, this is a dead end, because all we know is that
$a_n$ tends to
$\log(2)$ faster than
$\frac{1}{2n}$ tends to zero. If we want to continue this analysis we need a lower bound for
$\log(2)-a_n$.
