Injectivity and surjectivity of a recursive function

Question

Let $f:\mathbb{N} \to \mathbb{Q}^+$ defined as follows : $$\begin{cases} f(0) = 0 \\ f(2n) = \dfrac{1}{f(n)+1} \\ f(2n+1) = f(n)+1 \end{cases}\,.$$ It is asked to prove the injectivity then the surjectivity of $f$.

After examining first values taken by $f$, I proved by induction that $f(2^k)=\dfrac{F_k}{F_{k+1}}$ where $(F_n)$ is the fibonacci sequence. Also one notes that if $m$ and $n$ have different parity then we can't have $f(m) = f(n)$ since $f(2\mathbb{N}) \subset (0,1)$ and $f(2\mathbb{N}+1) \subset [1,+\infty)$.

Any ideas on how to finish the proof of injectivity and any thoughts about surjectivity are welcome.

Thanks

Answer 1

Edit: I think I've managed to finish the proof of surjectivity, but a sanity check would be greatly appreciated.

Suppose $n,m > 1$. As you say, $f(n) = f(m)$ implies $m \equiv n \pmod{2}$. In particular, by the definition of $f$ we get either $f(n/2) + 1 = f(m/2)+1$ or $(f((n-1)/2) + 1)^{-1} = (f((m-1)/2)+1)^{-1}$ depending on the parity of $n$ and $m$.

Taking inverses at the second equality, one can realize that both conditions can be stated at once as

$$ f(n) = f(m) \Rightarrow f(\lfloor n/2 \rfloor) = f(\lfloor m/2 \rfloor). $$

Now, suppose that $f$ is injective in $\{0, \dots, n\}$. Then if $m \in \{0, \dots, n\}$ and $f(n+1) = f(m)$, it must be that $f(\lfloor n+1/2 \rfloor) = f(\lfloor m/2 \rfloor)$.

Since both $\lfloor n+1/2 \rfloor$ and $\lfloor m/2 \rfloor$ lie on $\{0, \dots,n\}$, by hypothesis we have that $\lfloor n+1/2 \rfloor = \lfloor m/2 \rfloor$. Hence

$$ 1 > \left|\frac{n+1}{2} - \frac{m}{2}\right| = \frac{1}{2}(n+1-m) $$

and so $n+1-m < 2$ which proves that $n -1 < m$. Since $m \leq n$, it should be $m = n$ but this would imply $n \equiv n+1 \pmod{2}$, a contradiction.

We therefore see that $f$ is injective in $\{0, \dots, n+1\}$, and inductively this proves that $f$ is injective in the whole domain.

As for surjectivity, consider

$$ a_0 \in \mathbb{N}_0, \quad a_{k+1} := 2a_{k}+1. $$

This sequence satisfies that

$$ f(a_{k+1}) = f(a_k) + 1 = \dots = f(a_0) +k, \tag{1} $$

and so taking $a_0 = 0$ we see that $f(\mathbb{N}) \supset \mathbb{N}$. Likewise we get

$$ f(2a_{k}) = \frac{1}{f(a_{k})+1} = \frac{1}{f(a_0) + k-1+1} = \frac{1}{f(a_0)+k}. \tag{2} $$

Once again, for $a_0 = 0$ this says that $\{\frac{1}{k}\}_{k \geq 1 } \subset f(\mathbb{N})$. Equation $(1)$ also tells us that if we solve the equation $f(j) = p/q$ for $p < q$ natural then $f$ is surjective, as every positive rational number is of the form $n + p/q$ with $n,p,q \in \mathbb{N}_0$ and $p < q$. As you have noted $j$ will have to be even.

In other words, we can reduce the problem to solving the equation

$$ f(2l) = \frac{p}{p+s} \tag{3} $$

for all $p,s \geq 1$ and we have already proven that this is solvable for $p = 1$.

Once again, we proceed by induction: suppose $(3)$ is solvable for all naturals lower than $p'$. Then,

$$ f(2l) = \frac{p'}{p'+s} \iff \frac{1}{f(l)+1} = \frac{p'}{p'+s} \iff f(l)+1 = \frac{p'+s}{p'} $$

and rewriting the latter, equivalently it is

$$ p'(f(l)+1) = p'+s \iff p'f(l) + p' = p' +s \iff p'f(l) = s $$

and so if $s = p'q + r$ with $r < p'$ we get

$$ f(l) = \frac{s}{p'} = q + \frac{r}{p'}. $$

Since by hypothesis $f(2l') = r/p'$ has a solution (because $r < p'$) we can set $a_0 = 2l'$ and then by $(1)$ it is

$$ f(a_{q+1}) = f(a_0) + q = q + f(2l') = q + \frac{r}{p'}. $$

Taking $l = a_{q+1}$, we conclude the inductive step, proving that $f$ is surjective.

Answer 2

The function is given in the OEIS as $\, f(n) = a_n/b_n \,$ where the sequence $a_n$ is OEIS sequence A245327 and $b_n$ is OEIS sequence A245323. One interpretation of the pair of sequences $\,(a_n,b_n)\,$ is they are the steps in the subtraction-based Euclidean algorithm. They are a variant of the Calkin-Wilf tree or Stern-Brocot tree.

More precisely, the recursion is $\,f(2n+1)=1+f(n),\: f(2n)=1/(1+f(n)).$ This means that if we have a rational $\, a/b > 1\,$ then we subtract $1$ from it which gives the $\,f(2n+1)\,$ recursion step. If $\, 0 < a/b < 1\,$ then we take the reciprocal and subtract $1$ from it which gives the $\,f(2n)\,$ recursion step. Every positive rational get reduced to $1 = f(1)$ eventually and then we stop, but $\,f(0) = 0\,$ is a special initial case.

Answer 3

First we show $f$ is injective . . .

Suppose otherwise.

Let $a$ be the least positive integer such that $|f^{-1}\bigl(f(a)\bigr)| > 1$.

It's easily seen that $f(n)=1$ if and only if $n=1$, hence $a > 1$.

Let $b$ be a positive integer with $b > a$ such that $f(a)=f(b)$.

If $a$ is even, then so is $b$, hence \begin{align*} &f(a)=f(b)\\[4pt] \implies\;&\frac{1}{f\left({\large{\frac{a}{2}}}\right)+1}=\frac{1}{f\left({\large{\frac{b}{2}}}\right)+1}\\[4pt] \implies\;&f\left({\small{\frac{a}{2}}}\right)=f\left({\small{\frac{b}{2}}}\right)\\[4pt] \end{align*} contradicting the minimality of $a$.

Similarly, if $a$ is odd, then so is $b$, hence \begin{align*} &f(a)=f(b)\\[4pt] \implies\;&f\left({\small{\frac{a-1}{2}}}\right)+1=f\left({\small{\frac{b-1}{2}}}\right)+1\\[4pt] \implies\;&f\left({\small{\frac{a-1}{2}}}\right)=f\left({\small{\frac{b-1}{2}}}\right)\\[4pt] \end{align*} again contradicting the minimality of $a$.

Therefore $f$ is injective.

Next we show $f$ is surjective . . .

Let $\mathbb{Z}^{+}$ denote the set of positive integers, and let $\mathbb{Q}^{+}$ denote the set of positive rational numbers.

For $x\in \mathbb{Q}^{+}$, let $w(x)=p+q$, where $x={\large{\frac{p}{q}}}$, with $p,q\in \mathbb{Z}^{+}$ and $\gcd(p,q)=1$.

Our goal is to show $ \mathbb{Q}^{+}\subseteq f(\mathbb{Z}^{+})$.

Suppose otherwise.

Choose $x\in \mathbb{Q}^{+}$ such that $w(x)$ is least among all elements of $\mathbb{Q}^{+}$ which are not elements of $f(\mathbb{Z}^{+})$.

Write $x={\large{\frac{p}{q}}}$, where $p,q\in \mathbb{Z}^{+}$ and $\gcd(p,q)=1$.

Since $f(1)=1$, it follows that $p\ne q$.

If $p < q$, then by minimality of $w(x)$, we have $$f(n)=\frac{q-p}{p}$$ for some positive integer $n$, hence $$f(2n)=\frac{1}{f(n)+1}=\frac{1}{{\large{\frac{q-p}{p}}}+1}=\frac{p}{q}$$ contradiction.

Similarly, if $p > q$, then by minimality of $w(x)$, we have $$f(n)=\frac{p-q}{q}$$ for some positive integer $n$, hence $$f(2n+1)=f(n)+1=\frac{p-q}{q}+1=\frac{p}{q}$$ contradiction.

It follows that $f$ is surjective.