Spring 2016, problem 18

Does there exist a bijective map $f:\mathbb{N} \rightarrow \mathbb{N}$ so that $\sum^{\infty}_{n=1}\frac{f(n)}{n^2}$ is finite?

Comments

Nelix

5 years ago

Such a map does not exist. Actually, this remains true, if we merely require $f$ to be injective .

Proof:

The proof hinges on this simple statement:

Let $a > b$ and $A > B$ , then:

$$ a A + b B > a B + b A \; (Eq.0)$$

Here's the basic ideas:

Consider the finite sum $\sum_{n=1}^N f(n) \frac{1}{n^2}$
pick two indices: $i$ and $j$
Is f(i) < f(j)?
If no, what happens, when you exchange the values of $f$ at $i$ and $j$ with each other?
By (Eq.0), the sum gets smaller! This is the crucial point.
By a series of such swaps you get to the case f(1) < f(2) < f(3) <. .. and you only ever made the sum smaller.
Now redefine f(i) := i. You do not make the sum larger that way.
You now have the sum $H_N = \sum_{n=1}^{N} n \frac{1}{n^2}$. This one is smaller, than the original sum.
But as $N$ goes to $\infty$, $H_N$ goes to $\infty$.
Therefore the original sum does, too.

The argument doesn't really depend on the fact, that the problem authors picked $\frac{1}{n^2}$ and not something like $\frac{1}{n^\frac{3}{2}}$, say. Here's how it works in a formal way:

Let $f$ be an arbitrary injection $\mathbb{N} \rightarrow \mathbb{N}$ and let $(a_n)_{n \in \mathbb{N}} $ be a strictly decreasing sequence of positive real numbers. We will show, that

$$ \sum_{n=1}^N f(n) a_n >= \sum_{n=1}^N n a_n \; (Eq.1)$$.

Recalling that $\sum_{n=1}^{\infty} \frac{1}{n} = \infty$, the problem is then solved by setting $a_n := \frac{1}{n^2}$, The proof of $(Eq.1)$ is by mathematical induction over $N$:

The base case $N=1$ is obvious. So assume, that we have proved (Eq. 1) for all numbers smaller than $N$ in place of $N$. Let $i$ be the argument in the range $\{1, 2, ..., N\}$, at which $f$ becomes maximal: $$ \forall j \in \{1, 2, ...,N\} \setminus \{i\}: f(i) > f(j)$$ Certainly $f(i) >= N$, since the maximum of $N$ pairwise different natural numbers is at least $N$. If it so happens, that $i=N$ (Case 1), then we use the induction assumption, to bring the argument to a conclusion in the following manner:

$$ \sum_{n=1}^N f(n) a_n = f(N) a_N + \sum_{n=1}^{N-1} f(n) a_n >= N a_N + \sum_{n=1}^{N-1} n a_n = \sum_{n=1}^{N} n a_n$$

And we're finished. So assume, that $i \lt N$ (Case 2). Now define a function $g: \mathbb{N} \rightarrow \mathbb{N}$ by:

$$ \begin{eqnarray} &g(i) &:= f(N) \\ &g(N) &:= f(i) \\ \forall j \in \mathbb{N} \setminus \{i,N\}: &g(j) &:= f(j) \end{eqnarray}$$.

Then (this is where (Eq.0) comes into play):

$$\sum_{n=1}^N f(n) a_n - \sum_{n=1}^N g(n) a_n = (f(i) - f(N)) (a_i - a_N) > 0$$

or:

$$\sum_{n=1}^N f(n) a_n > \sum_{n=1}^N g(n) a_n \; (Eq.2)$$.

But $g$ is a injection, too, and $g(i)$ (when restricted to the range $i \in \{1, 2, ..., N\}$) becomes maximal for $i = N$. So we're back to (Case 1) (with $g$ in place of $f$ now) and conclude as above:

$$\sum_{n=1}^N g(n) a_n >= \sum_{n=1}^{N} n a_n \; (Eq.3)$$

Combine equations (Eq.2) and (Eq.3):

$$\sum_{n=1}^N f(n) a_n >= \sum_{n=1}^{N} n a_n$$

Done.

Hubert

5 years ago

no, here Nelix would say that all the $f(n)$ being different, $\sum_{q=n}^{2n}\frac {f(q)}{q^2}\ge \frac 1{4n^2}\sum_{q=n}^{2n}f(n)\ge \frac 1{4n^2}\sum_{q=1}^n q=\frac {n+1}{8n}\longrightarrow \frac 18\neq 0$
and what about $\sum_{q=1}^{n}\frac {f(q)}{q^3}$ now ? this converges for $f(n)=n$ but diverges if $f(2n)=n^2$ and $f(2n+1)=$ the $n+1$ th integer which is not a square, because the serie contains all the terms $\frac 1{8n}$, done

Hi, Hubert.

I agree with your first point completely. It's a very neat one-liner, that answers the problem satisfactorily: $\sum_{n=1}^{\infty} f(n) \frac{1}{n^2}$ is not a Cauchy series. But one may still ask, whether there is something peculiar going on with the particular choice of the sequence $\frac{1}{n^2}$, or if there is something more general behind.

In the second point, you seem to construct a counterexample to the more general statement $$\sum_{n=1}^{N} f(n) a_n >= \sum_{n=1}^{N} n a_n \; (Eq.1)$$ for every strictly decreasing sequence $(a_n)_{n \in \mathbb{N}}$. But here is my objection:

You set $a_n = \frac{1}{n^3}$ and state correctly, that for some choice of $f(n)$ the expression $\sum_{n=1}^{\infty} f(n) a_n$ diverges, whereas it converges for the choice $f(n) := n$. But this is not a counterexample. I didn't claim, that $\sum_{n=1}^{\infty} f(n) a_n$ diverges if and only if $\sum_{n=1}^{\infty} n a_n$ diverges. I claim only one direction of the if and only if:

If $\sum_{n=1}^{\infty} n a_n$ diverges, so does $\sum_{n=1}^{\infty} f(n) a_n$. This is - and no more - is a direct consequence of (Eq.1). No contradiction here, since $\sum_{n=1}^{\infty} n \frac{1}{n^3}$ doesn't diverge.

Indeed, for every (strictly decreasing, positive) choice of $(a_n)_{n \in \mathbb{N}}$, you can easily construct examples of $f(n)$, where $\sum_{n=1}^{\infty} f(n) a_n$ diverges.

Nelix 5 years ago