Convergence of exponentially decaying sublinear sequence

Question

I am looking at the following sequence: $$a_n = \sum_{k=1}^n \frac{r^{n-k}}{k}, \qquad 0 < r < 1.$$

I believe that this sequence converges to $0$ (https://www.desmos.com/calculator/frdzgqwoqd). I am wondering at what rate, that is, for which $n$ do we have $a_n \leq \epsilon$? Do you have an idea for how to find this rate?

More generally, can we say that the sequence $$b_n = \sum_{k=1}^n r^{n-k} \cdot c_k, \qquad 0 < r < 1$$ converges to $0$ where $d_n = \sum_{k=1}^n c_k$ is sublinear in $n$? Is it possible to say something about the rate of convergence depending on the convergence rate of $d_n$? That is, I am looking for a statement such as: If $\frac{d_n}{n} \leq \delta$ for all $n \geq N(\delta)$ then $b_n \leq f(N(\delta))$ for some function $f$.

Answer 1

What turned out to be good enough for me is the following, which works when $c_n$ is monotonically decreasing. In this case, $$(1-r) b_n = (1-r) \sum_{k=1}^n r^{n-k} c_k \leq \frac{1}{n} \sum_{k=1}^n c_k = \frac{d_n}{n}.$$

Here is why: As $r^{n-k}$ is monotonically increasing in $n$ and $c_n$ is monotonically decreasing in $n$, the inequality is tightest when $c_k \equiv c$ for some $c \in \mathbb{R}$, and hence, it is sufficient to consider this case. For this case, \begin{align*} (1-r) \sum_{k=1}^n r^{n-k} c = c (1-r) \sum_{k'=1}^n r^{k'} = c (1-r) \frac{1}{(1-r)} = c = c = \frac{1}{n} \sum_{k=1}^n c. \end{align*}

Answer 2

Yes, you can find the rate of convergence of $b_n$ in terms of $d_n$ using Abel’s summation formula.

Here’s how it would work,

$$b_n \ = \ \sum_{k=1}^n{c_k r^{n-k}} \ = \ r^n \ \sum_{k=1}^n{c_k r^{-k}} \tag{1}$$

$$= r^n \left(d_n \cdot r^{-n} - \int_1^n{d_{[t]} \cdot (-\log r \cdot r^{-t-1}) \ dt} \right) \tag{2}$$

$$= d_n \ + \ \log r \left(\int_1^n{d_{[t]} \cdot r^{n - t - 1} \ dt} \right). \tag{3}$$

where step $(2)$ came from using the formula.

So if you know what $d_n$ is, then substituting into $(3)$ will give you a formula for $b_n$. You should also expect significant cancellation between the first term and the integral.