Return to Answer

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))$. We can then take the limit $N\rightarrow \infty$.

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

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$ 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))$. We can then take the limit $N\rightarrow \infty$.

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))$. We can then take the limit $N\rightarrow \infty$.

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$ 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$ 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))$. We can then take the limit $N\rightarrow \infty$.

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$ 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))$. We can then take the limit $N\rightarrow \infty$.