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

Question

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.

Answer 1

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$ $<k_{i+1}\}$. 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. ■

Answer 2

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$.

Answer 3

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.