My students found an old problem given in my school in 2007 (probably from a Honor Calculus class) and had been trying to solve for some time. Here is the problem:
Prove or disprove: there exists a bijection $a$ from $\mathbb N$ onto $\mathbb Q$ such that $\sum_{n=1}^\infty (a_n-a_{n+1})^2$ is convergent. (With $a_n=a(n)$)
I have to confess that I am clueless on the method to deal with this problem. My intuition is that the sum represents the square of the distance traveled when visiting all rational numbers, but there is so many rationals that the sum should be infinite. On the other hand, the density of Q means that I can travel the distance between consecutive rationals of my travel can be arbitrarily small, so I am confused…
The only thing we could prove is that $\sum(a_n-a_{n+1})$ is divergent (otherwise, $\{a_n\}$ would be bounded, a contradiction).
Any clue is welcome.
Best Answer
My intuition says yes (there exists). Choose $a$ so that $a_n-a_{n+1}\leq \frac{1}{n}$; since $\sum_n\frac{1}{n^2}$ converges, if you can indeed choose one such $a$ you should be fine. Now, because $\sum_n\frac{1}{n}$ diverges, you could in principle take steps that are roughly that length and still get to 'cover all of $\mathbb{Q}$'. I might try and make this more precise.
EDIT: Making it precise.
Choose any bijection $f:\mathbb{N}\longrightarrow \mathbb{Q}$. We will obtain $a$ from $f$ inductively as follows.
First, let $a(1)=f(1)$. Now, if $|f(2)-a(1)|\leq \frac12$, we set $a(2)=f(2)$. Otherwise, we set $a(2)=a(1)\pm\frac12$, whichever sign brings $a(2)$ closer to $f(2)$. Then, if |$f(2)-a(2)|\leq \frac13$, we set $a(3)=f(2)$; otherwise we set $a(3)=a(2)\pm \frac13$, whichever signs brings $a(3)$ closer to $f(2)$. We proceed in this manner until we each $f(2)$, then we move onto $f(3)$, and so on.
Observations:
These observations guarantee that this inductive process can always continue and will eventually reach every rational. It uses the axiom of choice near the end, and I believe there's a way not to use it: look for
\begin{align} &a(k) \pm \tfrac1k\\ &a(k) \pm \tfrac1k \mp\tfrac{1}{2k}\\ &a(k) \pm \tfrac1k \mp\tfrac{1}{2k}\pm\tfrac{1}{4k}\\ &a(k) \pm \tfrac1k \mp\tfrac{1}{2k}\pm\tfrac{1}{4k}\mp\tfrac{1}{8k}\\ &\dots \end{align}
until you find one that's not yet been used. But honestly I'm not too worried about it.