Prove the surjectivity of $f(r,m)$ from $\mathbb{Z^{+}} \times \mathbb{N} \rightarrow 2\mathbb{N}+1$

Question

I'm trying to prove the bijectivity of some function and already have the injective proof down, but am having trouble with the surjectivity. I have to prove the following function, $f$, is surjective to the positive odd integers.

For some function $f(r,m) = 2^{r+1}m + \frac{2^{r}(5+(-1)^{\left\lceil\frac{r+2}{2}\right\rceil}+3(-1)^{\left\lfloor\frac{r+2}{2}\right\rfloor})-1}{5}$, $r \in \mathbb{Z^{+}}$ and $m \in \mathbb{N}$

Prove $f(r,m): \mathbb{Z^{+}} \times \mathbb{N} \rightarrow 2\mathbb{N}+1$

It seems like at each r-value the function produces odds that are a subset of the positive odd integers, but I can't find a way to prove surjectivity to the positive odds. I have a map of some values below so you can see how it jumps back and forth.

$f$ to odd integers">

Answer 1

Unless I'm missing some completely elegant solution, I believe the key idea of solving this problem is to observe the pattern in what $f$ gives when $m = 0$, in base $2$. I define the additive factor for some $r$ as $2^{r+1}$, as for a fixed $r$, $f(r,m)$ just serves as a linear function with common difference $2^{r+1}$.

\begin{array}{|c|c|r|} \hline r & f(r,0) & f(r,0) \text{ in base $2$, and additive factor} \\ \hline 1 & 1 & 00\color{blue}{0001}\\ & & 000100 \\ \hline 2 & 7 & 00\color{blue}{0111} \\ & & 001000 \\ \hline 3 & 11 & 00\color{blue}{1011} \\ & & 010000 \\ \hline 4 & 3 & 00\color{blue}{0011} \\ & & 100000 \\ \hline 5 & 19 & 0\color{blue}{0001}\color{red}{0011} \\ & & 0001000000 \\ \hline 6 & 115 & 00\color{blue}{0111}\color{red}{0011} \\ & & 0010000000 \\ \hline 7 & 179 & 00\color{blue}{1011}\color{red}{0011} \\ & & 0100000000 \\ \hline 8 & 51 & 00\color{blue}{0011}\color{red}{0011} \\ & & 1000000000 \\ \hline 9 & 307 & 00\color{blue}{0001}\color{red}{0011}\color{red}{0011} \\ & & 00010000000000 \\ \hline 10 & 1843 & 00\color{blue}{0111}\color{red}{0011}\color{red}{0011} \\ & & 00100000000000 \\ \hline \end{array} Whatever numbers on the right (i.e. when $m > 0$) would just be $f(r,0)$ plus some multiple of the additive factor. This motivates us to prove the following statements:

Lemma #1: Let $n \in \mathbb{Z}^+$ be odd, and consider the digits $n$ in base $2$. Suppose the last five digits are not $10011$. Let $n'$ be the number corresponding to the last five digits of $n$ (e.g. if $n = 11100011$, then $n' = 00011 = 11$). Then exactly one of the following holds:

• $n' = \color{blue}{0001} + c(100)$ for some $c \in \mathbb{N}$.
• $n' = \color{blue}{0111} + c(1000)$ for some $c \in \mathbb{N}$.
• $n' = \color{blue}{1011} + c(10000)$ for some $c \in \mathbb{N}$.
• $n' = \color{blue}{0011} + c(100000)$ for some $c \in \mathbb{N}$.

Proof. We simply exhaust all possible cases of $n$. Since $n$ is odd, the last digit must be $1$.

00001 = 00001            (Case 1)
00011 = 00011            (Case 4)
00101 = 00001 + 1(100)   (Case 1)
00111 = 00111            (Case 2)
01001 = 00001 + 2(100)   (Case 1)
01011 = 01011            (Case 3)
01101 = 00001 + 3(100)   (Case 1)
01111 = 00111 + 1(1000)  (Case 2)
10001 = 00001 + 4(100)   (Case 1)
10011                    (Excluded)
10101 = 00001 + 5(100)   (Case 1)
10111 = 00111 + 2(1000)  (Case 2)
11001 = 00001 + 6(100)   (Case 1)
11011 = 01011 + 1(10000) (Case 3)
11101 = 00001 + 7(100)   (Case 1)
11111 = 00111 + 3(1000)  (Case 2)

$\blacksquare$

Note that the "exactly once" part is part of the conclusion that $f$ is injective, so you don't need to prove that. With this, you should be able to extend the lemma inductively to prove the following:

Proposition #1: Let $n \in \mathbb{Z}^+$ be odd, and consider the digits $n$ in base $2$. Suppose $n$ has $N$ digits, and: \begin{gather*} N = d_Nd_{N-1} \dots d_{M+4}d_{M+3}d_{M+2}d_{M+1}d_M\underbrace{\color{red}{00110011\dots0011}}_{k \text{ blocks total}} \\ d_{M+4}d_{M+3}d_{M+2}d_{M+1}d_M \neq 10011 \end{gather*}

Let $n' = d_{M+4}d_{M+3}d_{M+2}d_{M+1}d_M$ digit-wise. Then exactly one of the following holds:

• $n' = \color{blue}{0001} + c(100)$ for some $c \in \mathbb{N}$.
• $n' = \color{blue}{0111} + c(1000)$ for some $c \in \mathbb{N}$.
• $n' = \color{blue}{1011} + c(10000)$ for some $c \in \mathbb{N}$.
• $n' = \color{blue}{0011} + c(100000)$ for some $c \in \mathbb{N}$.

Finally, you want to show that the pattern that we see in the table indeed holds. Formally, you want to show the following:

Proposition #2: Let $r \in \mathbb{Z}^+$. Suppose $r = 4p + q$, where $p \in \mathbb{N}$ and $q \in \mathbb{Z}^+$, $0 \leq q \leq 3$.

• If $q = 1$, then in base $2$, $f(r,0) = 0001\underbrace{\color{red}{00110011 \dots 0011}}_{p \text{ blocks total}}$.
• If $q = 2$, then in base $2$, $f(r,0) = 0111\underbrace{\color{red}{00110011 \dots 0011}}_{p \text{ blocks total}}$.
• If $q = 3$, then in base $2$, $f(r,0) = 1011\underbrace{\color{red}{00110011 \dots 0011}}_{p \text{ blocks total}}$.
• If $q = 0$, then in base $2$, $f(r,0) = 0111\underbrace{\color{red}{00110011 \dots 0011}}_{p \text{ blocks total}}$.

Proof. We have already verified that this is true for $p = 0$. For $p > 0$, we can re-express these expressions in base $10$, and for the first case this would be the result: \begin{align*} 0001\underbrace{\color{red}{00110011 \dots 0011}}_{p \text{ blocks total}} &= 2^{4p} + 3(2^{4p-4} + 2^{4p-8} + \cdots + 2^4 + 2^0) \\ &= 2^{4p} + 3\left(\frac{2^{4p} - 1}{2^4 - 1}\right) \\ &= 2^{4p} + \frac{2^{4p} - 1}{5} \\ &= \frac{3(2^{r}) - 1}{5} \end{align*}

We can conclude similarly that, for the next three cases, we have: \begin{align*} \frac{9(2^{r}) - 1}{5}, \;\frac{7(2^{r}) - 1}{5}, \; \frac{2^{r} - 1}{5} \end{align*}

It remains to check that $f(r,0)$ indeed yields these expressions. To do this, split $r$ in the 4 cases (modulo $4$), and conclude what are the possible values of $\left((-1)^{\left\lceil\frac{r+2}{2}\right\rceil}, (-1)^{\left\lfloor\frac{r+2}{2}\right\rfloor}\right)$. $\blacksquare$

With Proposition #1 and #2, we can then conclude that $f$ is surjective.

Answer 2

Write the function $f$ as follows: \begin{align} &f(r,m)=2^{r+1}m+\frac{2^rg(r)-1}5& g(r)=5-(-1)^{\lceil r/2\rceil}-3(-1)^{\lfloor{r/2\rfloor}} \end{align} Then for every $r$ we have:

• $g(r)\equiv 1\pmod 2$;
• $g(r)\equiv 2^{-r}\pmod 5$;
• $1\leq g(r)\leq 9$.

Let $n$ be a positive odd integer. There exists, and are uniquely determined, $r>0$ and $q$ odd such that $$5n+1=2^rq\tag 1$$ Then we have $2^rq\equiv 1\pmod 5$ and $q\equiv 1\pmod 2$, hence $q\equiv g(r)\pmod 5$ and $q\equiv g(r)\pmod 2$, from which follows $q\equiv g(r)\pmod{10}$. Since $1\leq g(r)\leq 9$, this implies $g(r)=q\bmod{10}\leq q$.

On the other hand $5n+1\equiv 2^rg(r)\pmod{2^{r+1}}$ gives $n\equiv f(r,0)\pmod{2^{r+1}}$. Thus $$m=\frac{n-f(r,0)}{2^{r+1}}=\frac{2^r(q-g(r))}5$$ is a non-negative integer and we have $n=f(r,m)$, thus proving $f$ to be surjective.