# If $\sum_{n=1}^{\infty}{a_{[f(n)]}}$ converges, then $\sum_{n=1}^{\infty}{\frac{a_n}{f(n)}}$ converges.

I am trying to determine whether the following statement is true or false:

Let $$a_n$$ be a decreasing positive sequence such that $$\displaystyle \sum \limits _{n=1}^\infty a_n$$ diverges, and let let $$f$$ be a function such that $$\lim\limits_{n\to\infty} f(n) = \infty$$.

If $$\displaystyle \sum \limits _{n=1}^\infty a_{[f(n)]}$$ converges, then $$\displaystyle \sum \limits _{n=1}^\infty \frac{a_n}{f(n)}$$ converges.

I tried to use the comparison test but could not find any candidates.

It does seems the second sum is smaller than the first, but finding an upper bound didn't work either.

This question is from our calculus course booklet, expert difficulty level.

Any hints will be appreciated.

• What have you tried? Jun 3, 2022 at 15:01
• Hint: lim inf of a(n) Jun 3, 2022 at 16:00
• @barrycarter $a_n$ must converge to zero in order for the statement to be true. Whats the hint here? Jun 3, 2022 at 16:03
• @aaabbb You're right, I was overthinking it. I was thinking a(n) effectively becomes a constant and both a(f(n)) and a(n)/f(n) are essentially taking every f(n)th element, and thus equal. The fact that a(n) must converge to 0 makes it easier than that, I think Jun 3, 2022 at 16:07
• My edit was for typos. You had subscript "$i$" for "$n$" in the summations. Jun 3, 2022 at 18:52

Further below shows convergence of $$\sum_{n=1}^{\infty}\frac{a_n}{f(n)}$$ is guaranteed if the $$a_n$$s are nonincreasing. This just below was my original answer however which did not assume the $$a_n$$ are nonincreasing. This shows that the $$a_n$$s nondecreasing is essential to guarantee that the sum $$\sum_{n=1}^{\infty}\frac{a_n}{f(n)}$$ converges. What about $$a_n$$ defined as follows: $$a_n = n$$ if $$3$$ does not divide $$n$$, and $$a_n = 0$$ otherwise, or equivalently, if $$n$$ is a multiple of $$3$$. Then define $$f(n) = 3n$$.

Then on the one hand, $$\sum_{n=1}^{\infty} \frac{a_n}{f(n)}$$ diverges; $$\frac{a_n}{f(n)}$$ is nonnegative for all $$n$$ and is $$\frac{1}{3}$$ for each $$n$$ that is not divisible by $$3$$ and there are an infnite number of such $$n$$. On the other hand, $$\sum_{n=1}^{\infty} a_{|f(n)|}$$ is $$0$$ as $$f(n)$$ is a multiple of $$3$$ for all $$n$$ and $$a_m$$ is $$0$$ for all $$m$$ that is a multiple of $$3$$.

ETA: Here we show that if the $$a_n$$s are also nonincreasing, then convergence of the infinite sum $$\sum_{n=1}^{\infty}\frac{a_n}{f(n)}$$ is guaranteed.

IF however the $$a_n$$ are nonincreasing it is a different story:

THM 1. Let $$\{a_n\}; n=1,2,\ldots$$ be a nonincreasing sequence of positive numbers, and let $$\{f(n)\}; n=1,2,\ldots$$ be a sequence of positive integers such that $$\lim_{n \rightarrow \infty} f(n)$$ is $$\infty$$. Furthermore, suppose that $$\sum_{n=1}^{\infty} a_{f(n)}$$ is finite. Then $$\sum_{n=1}^{\infty} \frac{a_n}{f(n)}$$ is also finite.

We now note that we do not assume anything else about $$f$$; in particular $$f$$ is not assumed to be increasing nor injective.

To prove THM 1, let $$A$$ be the set $$A=\{n; f(n)>n\}$$ and let $$B$$ be the remaining set of integers, or equivalently, $$B=\{n; f(n)\le n\}$$. We now establish the following result:

Lemma 2. Let us assume the conditions of THM 1. Then $$\sum_{n \in B} \frac{a_n}{f(n)}$$ is finite.

Proof of Lemma 2: $$\sum_{n \in B} \frac{a_n}{f(n)} \le \sum_{n \in B} \frac{a_{f(n)}}{f(n)}$$ $$\le \sum_{n \in B} a_{f(n)},$$ the first inequality following from the $$a_i$$s nonincreasing in $$i$$ and $$f(n)\le n$$ for each $$n \in B$$.■

Remainder of Proof of THM 1: To finish the proof of THM 1, note that it suffices to show that $$\sum_{n \in A} \frac{a_n}{f(n)}$$ is finite. We do so next.

First, let $$F$$ be the set of integers $$k$$ such that there is at least one $$n$$ such that $$f(n)=k$$. Then write $$F =\{k_1,k_2,\ldots \}$$ where the $$k_i$$s are in increasing order, and if $$k_1>1$$, define an additional integer $$k_0=1$$. Then the conditions of THM 1 give $$\sum_{i=0}^{\infty} a_{k_i} \le a_1+ \sum_{n=1}^{\infty} a_{f(n)} < \infty.$$ Also, for each nonnegative integer $$i$$: $$a_{k_i} \ge \sum_{n=k_i}^{n=k_{i+1}-1} \frac{a_n}{k_{i+1}-k_i}$$ $$\ge \sum_{n=k_i}^{n=k_{i+1}-1}\frac{a_n}{k_{i+1}}.$$ [The first inequality follows from the $$a_n$$s nonincreasing.] Thus the following inequality is true: $$\sum_{i=0}^{\infty}\sum_{n=k_i}^{n=k_{i+1}-1} \frac{a_n}{k_{i+1}}$$ $$\le \sum_{i=0}^{\infty} a_{k_i} < \infty.$$

Now, let $$n$$ be an integer in $$A$$, and let $$i$$ be a nonnegative integer such that $$k_i \le n < k_{i+1}$$. Then $$f(n)>n$$ [because $$n \in A$$] and so $$f(n) \ge k_{i+1}$$ and thus the inequality $$\frac{a_n}{f(n)}\le \frac{a_n}{k_{i+1}}$$ holds for that particular $$n$$. So equivalently, now let $$i$$ be a nonnegative integer and define a subset $$A_i$$ of $$A$$ as follows: $$A_i =\{n \in A;$$ $$k_i \le n$$ $$. Then the $$A_i$$s partition $$A$$, and for each nonnegative integer $$i$$ and each $$n \in A_i$$ the inequality $$\frac{a_n}{f(n)}\le \frac{a_n}{k_{i+1}}$$ holds. Thus from this observation:

$$\sum_{n \in A} \frac{a_n}{f(n)} = \sum_{i=0}^{\infty}\sum_{n \in A_i} \frac{a_n}{f(n)}$$ $$\le \sum_{i=0}^{\infty}\sum_{n\in A_i}\frac{a_n}{k_{i+1}}$$ $$\le \sum_{i=0}^{\infty}\sum_{n=k_i}^{k_{i+1}-1}\frac{a_n}{k_{i+1}}$$ $$\le \sum_{i=0}^{\infty} a_{k_i}<\infty.$$ Thus indeed the inequality $$\sum_{n \in A}\frac{a_n}{f(n)}$$ $$<\infty$$ holds and so THM 1 follows. ■

• Is the sequence $$a_n=\begin{cases}\frac{1}{n},&3\mid n, \\ 0, & 3\nmid n\end{cases}$$ decreasing in $n$? Jun 3, 2022 at 18:52
• (+1) No problem, the edit history shows that OP removed that condition for an unknown reason and then reintroduced it, so the downvotes now seems unjust. Anyway, I skimmed over your argument, and it seems correct. Great work! One minor point: I guess your definition of $A_i$ should be: $$A_i = A\cap[k_i, k_{i+1}) = \{n \in A : k_i \leq n < k_{i+1} \}.$$ Jun 4, 2022 at 22:30
• Nevermind, I confused myself in a previous, now-deleted comment. It seems to work perfectly. Jun 4, 2022 at 22:59
• No worries @Sangchul Lee that was a good question you asked, I am thinking of putting in a line or two pointing that out...but yes the inequality if any does go our desired direction
– Mike
Jun 4, 2022 at 23:04
• @SangchulLee that is great I don't mind a bit
– Mike
Jun 10, 2022 at 21:28

Wlog $$f:\mathbb{N} \rightarrow \mathbb{N}$$.

1. Since $$a_k$$ is decreasing, then if $$f(k)\leq km$$ for some integer $$m$$ and $$\forall k\in\mathbb{N}$$ $$\sum_{k=1}^\infty a_{f(k)} \geq \frac{1}{m}\sum_{k=1}^\infty ma_{km} \geq \frac{1}{m}\sum_{k=1}^\infty \sum_{l=0}^{m-1}a_{km+l} \geq \frac{1}{m}\sum_{k=m}^\infty a_{k} = \infty \, .$$ Hence $$f(k)/k$$ can not be bounded and there are infinitely many $$N$$ with $$f(N)>N$$.

2. For such $$N$$ I consider the ordered set $$S=\{n,...,N,...,f(N)\}$$ and set $$F=f(S)=\{f(n),...,f(N),...,f\left(f(N)\right)\}$$. Let $$\sigma:S\rightarrow S$$ be a permutation of $$S$$ s.t. $$F_\sigma=f(\sigma(S))=\{f(\sigma(n)),...,f(\sigma(N)),...,f\left(\sigma(f(N))\right)\}$$ is in non-decreasing order. Then $$\sum_{k=n}^{f(N)} \frac{a_k}{f(k)} \leq \sum_{k=n}^{f(N)} \frac{a_k}{f(\sigma(k))}$$ by the rearrangement-inequality.

3. Finally \begin{align} \sum_{k=n}^{f(N)-1}\frac{a_k}{f(\sigma(k))} &= \sum_{\substack{k=n \\ f(\sigma(k))\leq k}}^{f(N)-1}\frac{a_k}{f(\sigma(k))} + \sum_{\substack{k=n \\ f(\sigma(k)) > k}}^{f(N)-1}\frac{a_k}{f(\sigma(k))} = S_{f\leq k} + S_{f>k} \end{align} and \begin{align} S_{f\leq k} \leq \sum_{\substack{k=n \\ f(\sigma(k))\leq k}}^{f(N)-1}\frac{a_{f(\sigma(k))}}{f(\sigma(k))} &\leq \sum_{\substack{k=n}}^{f(N)-1}\frac{a_{f(\sigma(k))}}{f(\sigma(k))} \leq \sum_{\substack{k=1}}^{\infty}a_{f(k)} < \infty \\ S_{f>k} - \sum_{\substack{k=n \\ f(\sigma(k)) > k}}^{f(\sigma(n))-1}\frac{a_k}{f(\sigma(k))} &= \sum_{\substack{k=n}}^{M-1} \sum_{\substack{m=f(\sigma(k)) \\ f(\sigma(m))>m}}^{f(\sigma(k+1))-1} \frac{a_{m}}{f(\sigma(m))} \\ &\leq \sum_{\substack{k=n \\ \text{smallest } m \text{ s.t.} \\ f(\sigma(m))>m \geq f(\sigma(k))}}^{M-1} a_{f(\sigma(k))} \, \frac{f(\sigma(k+1))-f(\sigma(k))}{f(\sigma(m))} \\ &\leq \sum_{k=n}^{M-1} a_{f(\sigma(k))} \leq \sum_{k=1}^\infty a_{f(k)} < \infty \, ,\end{align} where $$M \in S$$ is s.t. $$\sigma(M)=N$$. Furthermore, since $$f(\sigma(k))$$ is non-decreasing and $$f(\sigma(m))>f(\sigma(k))$$, either $$f(\sigma(m))=f(\sigma(k+1))$$ or $$f(\sigma(m))>f(\sigma(k+1))$$. $$n$$ is chosen s.t. $$f(\sigma(n))\geq n$$ which is always possible since $$f\geq 1$$. We can then take the limit $$N\rightarrow \infty$$.

Suppose that $$f$$ is integer-valued and monotone increasing. Define $$\Delta = \sup_k \frac{f(k+1) - f(k)}{f(f(k))}.$$ If $$\Delta < \infty$$, then your claim is true.

Define $$I_0 = \{n : n < f(1)\}$$. For $$k \geq 1$$, define $$I_k = \Big\{\, n : f(k) \leq n < f(k+1)\,\Big\}.$$ Then note $$\sum_{n \geq 1} \frac{a_n}{f(n)} = \sum_{k\geq 0} S_k, \quad \mbox{where} \quad S_k :=\sum_{n \in I_k} \frac{a_n}{f(n)}.$$ Note that since $$a_n$$ is a decreasing positive sequence, and $$f$$ is increasing, then for $$k \geq 1$$, $$S_k \leq a_{f(k)} \Delta_k \quad \mbox{where} \quad \Delta_k := \frac{f(k+1) - f(k)}{f(f(k))}$$ Putting the pieces together, $$\sum_{n \geq 1} \frac{a_n}{f(n)} \leq S_0 + \Delta \sum_{k\geq 1} a_{f(k)} < \infty.$$ This is what you seek to prove.

I think the remaining question is what happens if $$\Delta = \infty$$. My feeling is that in this case, $$f$$ must "eventually grow faster than linear" such that the claim is automatically true.