# Convergence of $\sum\limits_{n=1}^{\infty} \frac{1}{nf(n)}$

This problem is taken from Vojtěch Jarník International Mathematical Competition 2010, Category I, Problem 1. — edit by KennyTM

On going through this post http://math.stackexchange.com/questions/2120/does-there-exist-an-f-mathbbn-to-mathbbn-such-that-sum-fn-n2-conve i happened to get the following 2 problems into my mind:

Let $f: \mathbb{N} \to \mathbb{N}$ be a bijection. Then does the series $$\sum\limits_{n=1}^{\infty} \frac{1}{nf(n)}$$ converge?

Next, consider the series $$\sum\limits_{n=1}^{\infty} \frac{1}{n+f(n)}$$ where $f: \mathbb{N} \to \mathbb{N}$ is a bijection. Clearly by taking $f(n)=n$ we see that the series is divergent. Does there exist a bijection such that the sum above is convergent?

-
Clearly, for the second question, if $f(n)$ satisfies $\lim_{n\to\infty}\frac{n}{f(n)}=0$ ($f(n)$ grows much faster than $n$), the second sum converges. – J. M. Sep 8 '10 at 9:42
J.M. It won't, since $f$ is a bijection, $n/f(n)\ge1$ infinitely often. – Robin Chapman Sep 8 '10 at 9:55
@Robin, mini-tip: when writing a comment to someone (even a commenter) you can prefix the name with an @ and s/he'll get a notice about it---like you about this one. – Mariano Suárez-Alvarez Sep 8 '10 at 10:07
@Robin: Hmm, on second thought, you're right. @Mariano: For me, sometimes it works, sometimes it doesn't. – J. M. Sep 8 '10 at 10:57
@Mariano: does one have to use the whole username, or @(user-first-name) suffices? e.g., are you getting a notice from this comment? – T.. Sep 8 '10 at 17:55

Hints. For the first series, prove that $$\sum_{n=1}^N\frac1{nf(n)}\le\sum_{n=1}^N\frac1{n^2}.$$

For the second, what would happen if $f$ were an involution, and in each pair $(n,f(n))$ one term was much bigger than the other?

-

A couple of proofs in italian.

-
The problem comes from the 2010 Vojtěch Jarník International Mathematical Competition ( vjimc.osu.cz ). – Fosco Loregian Sep 8 '10 at 9:34

For question $2$, consider any $f(n)$ which is $2^n$ for $n$ which are not powers of $2.$ This lets us divide our sum into two parts, both of which converge.

-