# Big O bound on the Tail of a Sum

Suppose we have a non-negative sequence $$\{a_j\}$$ such that $$\sum_{j=1}^{\infty}a_j for some finite constant $$L$$. My professor claims $$\sum_{j=k}^{\infty} a_j =O(\log^{-1} k)$$ but I am not sure how to derive this. I know $$\sum_{j=k}^{\infty} \frac{1}{j^p} = O(k^{1-p})$$ for $$p>1$$, and my handwaving answer is that $$k^{1-p}$$ has the same growth as $$\frac{1-p}{k^{p-1}-1}$$, so taking $$p\to 1$$ and applying L'Hopital we get that the tail for any convergent series has to be bounded by $$\log^{-1}(k)$$ but for this to work I think I would have to show $$a_j= O(\frac{1}{j^p})$$ for some $$p>1$$.

My professor suggested using that $$a_j =O(\frac{1}{j \log j})$$, but I don't know what I am supposed to use this for since the sum of $$\frac{1}{j \log j}$$ is divergent. If I could show there exists some $$\delta>0$$ for which $$a_j =O(\frac{1}{j^{1+\delta} \log j})$$, then I can show the claim with an integral comparison.

He also said this bound wasn't tight, so any suggestions on possible tighter bounds would be great!

## 1 Answer

That claim is wrong. The series remainder $$\sum_{j=k}^{\infty} a_j$$ of a converging series $$\sum_{j=1}^{\infty}a_j$$ converges to zero, but that convergence can be arbitrarily slow. Requiring that all $$a_j$$ are non-negative does not change that fact.

Let $$(r_k)$$ be an arbitrary decreasing sequence of real numbers with $$r_k\to 0$$ and set $$a_j = r_j - r_{j+1}$$. Then $$a_j \ge 0$$ and $$\sum_{j=1}^n a_j = r_1 - r_{n+1} \, ,$$ so that $$\sum_{j=1}^\infty a_j = r_1 < L := r_1 + 1$$. But the series remainder $$\sum_{j=k}^{\infty} a_j = r_k$$ can decrease to zero as slowly as you like.

For a concrete counterexample one can choose $$r_k = f(k)$$ with $$f(x) = \frac{\log(e + \log x)}{e + \log x}$$ which is decreasing on $$[1, \infty)$$ with $$\lim_{x \to \infty}\log(x)\cdot f(x) = +\infty$$.

• Thank you! That makes complete sense. Turns out we only needed the tail to be little o(1) for the theorem the professor used it in, but it is interesting to know we can't get a general big O bound on the tail for convergent sums. Nov 21, 2023 at 8:38