17
$\begingroup$

Is there a bijection $f: \mathbb{N} \rightarrow \mathbb{N}$ such that the series $\sum_1 ^\infty \frac{1}{n+f(n)} $ is convergent?

I could not solve this. I tried to proceed in following lines:

1) Tried to provide a contradiction:

First let $n \sim m$ iff $\exists k \in \mathbb{Z}$ such that $f^k(n)=m$. This is an equivalence relation. Consider the orbits. For the finite orbits we can compare the series to $\sum_1^\infty \frac{1}{n+n}$. But then I could not figure out how to proceed for infinite orbits.

2) Tried to prove that there is some function:

Let $\{k_n\}$ be a subsequence of $\mathbb{N}$ such that $\sum_0^\infty \frac{1}{k_n}$ converges. Set $f(n)=k_{n}, \forall n \in \mathbb{N}\setminus\{k_n\}$. Then images of each $n$ which are not in the subsequence $k_n$ is defined. Now we have to define images of each $k_n$. Define $f(k_n)=n$ $ \forall n \in \mathbb{N}\setminus \{k_n\}.$.

Could not proceed further. I think My second attempt was going in right direction. My plan was use the fact that all elements here are positive and to construct the function $f$ in such a manner that $\forall n\in \mathbb{N}$ either $n$ or $f(n)$ is in $\{k_n\}$.

$\endgroup$
  • 3
    $\begingroup$ Decompose $\mathbb N$ into the disjoint union of $S=\{k^2\mid k\in\mathbb N\}$ and $R=\mathbb N\setminus S$. Decompose $S$ into the disjoint union $\bigcup\limits_{k\in\mathbb N}S_k$, where the size of $S_k$ is $2k$ and every element of $S_k$ is smaller than every element of $S_{k+1}$, for every $k$. Then enumerate $R=\{r_k\mid k\in\mathbb N\}$ with $r_k<r_{k+1}$ for every $k$, reorder $\mathbb N$ as $$S_1\ r_1\ S_2\ r_2\ S_3\ \ldots\ S_k\ r_k\ S_{k+1}\ \ldots$$ and consider the corresponding function $f$. Then $$\sum_{n\in S}\frac1{n+f(n)}<\sum_{n\in S}\frac1{n}=\sum_k\frac1{k^2}$$ $\endgroup$ – Did Feb 17 '17 at 12:51
  • 1
    $\begingroup$ ... converges and $r_k\geqslant k^2$ for each $k$, hence $$\sum_{n\in R}\frac1{n+f(n)}<\sum_k\frac1{r_k}\leqslant\sum_k\frac1{k^2}$$ converges hence the whole series converges. $\endgroup$ – Did Feb 17 '17 at 12:51
  • $\begingroup$ @Did, I think you want to order $\mathbb{N}$ as $r_1,S_1,r_2,S_2,r_3,S_3,\ldots$ (providing that $0\notin\mathbb{N}$). But well, if $0\in \mathbb{N}$, then we have to modify this solution only slightly. I would give you an upvote if you posted this as a solution. $\endgroup$ – Batominovski Feb 17 '17 at 13:03
  • $\begingroup$ @Batominovski "I think you want to order N as r1,S1,r2,S2,r3,S3,…" Hmmm, why? What difference does it make? $\endgroup$ – Did Feb 17 '17 at 19:36
  • $\begingroup$ @Did The difference is that $f^{-1}\left(r_k\right)\geq k^2$ may not hold. You have $f^{-1}\left(r_k\right)\geq k^2-1$ instead. (However, nothing really changes.) $\endgroup$ – Batominovski Feb 18 '17 at 2:26
17
$\begingroup$

Originally, I gave this example:

$$f (n)=\begin{cases}k,&\ \text { if } n=3^k , \text { with $k $ not a power of $2$}\\ 2^{n-1} , &\ \text { otherwise }\end{cases}$$ (the idea is to push the small numbers further and further down the road so that when they appear they are compensated by the $n $). Then $$ \sum_n\frac1 {n+f (n)}<\sum_{k}\frac 1 {3^k+k}+\sum_n\frac1 {n+2^{n-1}}<\infty. $$

And it is the right idea, but the problem is that such $f$ is not onto. For instance, $2^{26}$ is not in the range of $f$, because when $n=27$, we are using the other branch of $f$ to get $3$.

So we need to tweak the example slightly. Let $$ T=\{3^k:\ k\ \text{ is not a power of } 2\}=\{3^3,3^5,3^6,3^7,3^9,\ldots\} $$ and $$ S=\mathbb N\setminus T=\{1,\ldots,7,8,10,11,\ldots\}. $$ Write them as an ordered sequence, $T=\{t_1,t_2,\ldots\}$ and $S=\{s_1,s_2,\ldots\}$. Now define $$ f(n)=\begin{cases} \log_3 n,&\ \text{ if }\ n=t_k\\ \ \\ 2^{k-1},&\ \text{ if }\ n=s_k \end{cases} $$ One can check explicitly that $$ g(m)=\begin{cases} 3^m,&\ \text{ if $m$ is not a power of $2$}\ \\ \ \\ s_{k+1},&\ \text{ if }\ m=2^k \end{cases} $$ is an inverse for $f$.

$\endgroup$
1
$\begingroup$

Not a new solution, just writing to clarify for myself how the solution of @Martin Argerami: works.

We want $\sum_{n\in \mathbb{N}} \frac{1}{n + f(n)} < \infty$. Consider a covering $\mathbb{N} = A\cup B$. It's enough to have $\sum_{n\in A} \frac{1}{n + f(n)} $, $\sum_{n \in B} \frac{1}{n + f(n)}< \infty$. So it's enoough to find $A$, $B$ so that $$\sum_{n \in A} \frac{1}{f(n)}= \sum_{n \in f(A)} \frac{1}{n} < \infty \\ \sum_{n \in B} \frac{1}{n} < \infty$$

So it's enough to have $B$ so that $\sum_{n\in B} \frac{1}{n} < \infty$ and $f$ mapping $A = \mathbb{N} \backslash B$ to $B$. There are many possibilities here.

$\endgroup$
  • $\begingroup$ I would not say that "this is how the other solution works" because the other solution relies heavily on infinite orbits while a simple involution between the powers of two and the non-powers of two works fine. $\endgroup$ – Phira Nov 19 '18 at 10:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.