Infinite series, injective function and rearrangement inequality Let $f:\mathbb{N^*}\to\mathbb{N^*}$ an injective function. Show that the following infinite series $$\sum_{i=1}^{\infty}\frac{f(n)}{n^2}$$ is divergent. I am supposed to deal with this using the rearrangement inequality. But I don't know how!Could some explain this to me step by step? I really want to understand...
 A: The rearrangement inequality says the partial sum $$\sum_{n=1}^M \dfrac{f(n)}{n^2} \ge \sum_{n=1}^M \dfrac{b_n}{n^2}$$
where $b_1, \ldots, b_M$ are $f(1), \ldots, f(M)$ rearranged into increasing order.  Since $b_n \ge n$, we get
$$ \sum_{n=1}^M \dfrac{f(n)}{n^2} \ge  \sum_{n=1}^M \dfrac{n}{n^2} =\sum_{n=1}^M \dfrac{1}{n}$$
Now what do you know about the sum on the right?
A: The goal is to use the rearrangement inequality to compare the series to the harmonic series
$$\sum_{n=1}^{\infty}\frac{1}{n},$$
which diverges. Consider a partial sum
$$S(N) = \sum_{n=1}^{N}\frac{f(n)}{n^2}.$$
Let $x_1,\ldots,x_N$ be the values of $f(n)$ for $1 \leq n \leq N$, labeled such that
$$x_1 \leq \ldots \leq x_N.$$
Let
$$y_j = \frac{1}{(N - j + 1)^2}$$
for $1 \leq j \leq N$. The rearrangement inequality tells us that
\begin{equation}
x_Ny_1 + \cdots + x_1y_N \leq x_{\sigma(1)}y_1 + \cdots + x_{\sigma(N)}y_N. \label{a}\tag{1}
\end{equation}
for any permutation $\sigma$ of $1,\ldots,M=N$. Choose $\sigma$ such that $x_{\sigma(j)} = f(N - j + 1)$ so that the right-hand side of $(1)$ is equal to
$$\frac{f(1)}{1} + \frac{f(2)}{4} + \cdots + \frac{f(N)}{N^2} = S(N).$$
Now we examine the left-hand side of $(1)$. Since $f$ is injective and $x_N$ is the largest of the $x_i$, it must be that $x_N \geq N$. By induction it follows that $x_j \geq j$ for $1 \leq j \leq N$. Therefore
$$1 + \frac{1}{2} + \cdots + \frac{1}{N} \leq x_Ny_1 + \cdots + x_1y_n.$$
We thus have
$$1 + \frac{1}{2} + \cdots + \frac{1}{N} \leq S(N),$$
hence your series diverges by the comparison test.
A: Here is a direct proof without the use of the rearrangement inequality.
For every $N$, you have
$$\sum_{n=N+1}^{3N} \frac{f(n)}{n^2} \geq \sum_{n=N+1}^{3N} \frac{f(n)}{(3N)^2} \geq \frac{N^2}{9N^2}$$
because the $f(n)$ for $n \in [N+1, 3N]$ are $2N$ distinct integers, so at least $N$ of them are greater than $N$.
So
$$\sum_{N+1}^{3N} \frac{f(n)}{n^2} \geq \frac{1}{9}$$
so the series is not Cauchy, so it diverges.
