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 is surjective to the positive odd integers. I have a proof I wrote below, but I am not sure if it is true.
For some function $\nu(r,m) = 2^{r+1}m + \frac{2^{r}(3-2(-1)^{r})-1}{3}$, $r \in \mathbb{Z^{+}}$ and $m \in \mathbb{N}$
Prove $\nu(r,m): \mathbb{Z^{+}} \times \mathbb{N} \rightarrow 2\mathbb{N}+1$
First, define $V_{r} = 2^{r+1}\mathbb{N} + \frac{2^{r}(3-2(-1)^{r})-1}{3}$, $r \in \mathbb{Z^{+}}$
The surjectivity proof is the same as showing that $\bigcup\limits_{r=1}^{\infty} V_{r} = 2\mathbb{N}+1$.
$\\$
Step 1:
Prove $\bigcup\limits_{r=1}^{\infty} V_{r} \subseteq 2\mathbb{N}+1$
Let $n \in \bigcup\limits_{r=1}^{\infty} V_{r}$, then $n \in V_{r}$ for some $r \in \mathbb{Z^{+}}$
$n = 2^{r+1}m + \frac{2^{r}(3-2(-1)^{r})-1}{3} = 2 \left( 2^{r}m + \frac{2^{r-1}(3-2(-1)^{r})-2}{3} \right) +1$
Now show $2^{r}m + \frac{2^{r-1}(3-2(-1)^{r})-2}{3} \in \mathbb{N}$. Obviously, $2^{r}m \in \mathbb{N}$ and for the fraction we have to show that $2^{r-1}(3-2(-1)^{r})-2 \equiv 0 \pmod{3}$. This is pretty easy knowing that $2^{even}\equiv 1\pmod{3}$ and $2^{odd}\equiv 2\pmod{3}$ and simplifying. We also prove the $\frac{2^{r-1}(3-2(-1)^{r})-2}{3} \geq 0$ to ensure the fraction is in the naturals.
Therefore, $2^{r}m + \frac{2^{r-1}(3-2(-1)^{r})-2}{3} \in \mathbb{N}$ and $\bigcup\limits_{r=1}^{\infty} V_{r} \subseteq 2\mathbb{N}+1$
$\\$
Step 2:
Prove $2\mathbb{N}+1 \subseteq \bigcup\limits_{r=1}^{\infty} V_{r}$
Let $n \in 2\mathbb{N}+1$
$n = 2k + 1$, $k \in \mathbb{N}$
Choose $k=2^{2}m$, $m \in \mathbb{N}$
$n = 2^{3}m + 1$, $m \in \mathbb{N}$
Now note that $V_{2} = 8\mathbb{N}+1$ so $n \in V_{2}$ and further $n \in \bigcup\limits_{r=1}^{\infty} V_{r}$. Therefore $2\mathbb{N}+1 \subseteq \bigcup\limits_{r=1}^{\infty} V_{r}$.
$\\$
Because Step 1 and Step 2 are true we can say that $\bigcup\limits_{r=1}^{\infty} V_{r} = 2\mathbb{N}+1$.
$\\$
Is there someplace where the proof is wrong? Is this the correct approach to prove surjectivity?
In Step 2 of your proof you assumed that $n$ can be written as $8m+1$ but that is not true for all integers. For example, $11$ can not be written in such a way. In fact if your proof was correct you would have shown that $V_2=\bigcup\limits_{r=1}^{\infty} V_r,$ so the function wouldn't be injective.
For each $r,$ we have that $V_r=2^{r+1}\mathbb{N}+k_r,$ for some integer $k_r\leq 2^{r+1}.$ Let us first prove that $V_{r+2}=4V_{r}+1$.
If $r$ is odd we have
\begin{align} V_{r+2}=2^{r+3}\mathbb{N}+\frac{5\cdot2^{r+2}-1}{3}&=4\cdot2^{r+1}\mathbb{N}+4\frac{5\cdot2^{r}-1/4}{3}\\ &=4(2^{r+1}\mathbb{N}+\frac{5\cdot2^{r}-1}{3})+1\\ &=4V_r+1. \end{align}
If $r$ ie even we have
\begin{align} V_{r+2}=2^{r+3}\mathbb{N}+\frac{2^{r+2}-1}{3}&=4\cdot2^{r+1}\mathbb{N}+4\frac{2^{r}-1/4}{3}\\ &=4(2^{r+1}\mathbb{N}+\frac{2^{r}-1}{3})+1\\ &=4V_r+1. \end{align} Moreover, since the function is injective we have $V_i\cap V_j \, \, \, \forall i\neq j.$ The important observation now is that if $n\not \in \bigcup\limits_{r=1}^{n} V_r$ then $n$ can also be written as $k+2^{r+1}$ for some integer $k\leq 2^{r+1}$. Let us prove this by induction.
For $r=1$ we have $V_1=4\mathbb{N}+3$ so if $n\not\in V_1$ we must have $n\equiv 1 \bmod 4.$
Let us now assume that the result is true for $r$ and prove it for $r+1$.
Since $n\not \in \bigcup\limits_{r=1}^{n+1} V_r,$ we obviously also have $n\not \in \bigcup\limits_{r=1}^{n} V_r,$ hence by the induction hypothesis we can assume that $n=k_r+2^{r+1}$ for some integer $k_r\leq 2^{r+1}$. So, we wil have that $n\equiv k_r \bmod 2^ {r+2}$ or $n\equiv k_r+2^{r+1} \bmod 2^{r+2}.$ Thus, if we can prove that either $V_{r+1}=2^{r+2}\mathbb{N}+k_r$ or $V_{r+1}=2^{r+2}\mathbb{N}+k_r+2^{r+1}$ we would have our induction step proved.
Suppose that this was not the case. Then, we would have $V_{r+1}=k+2^{r+2}$ and $k\not \equiv k_r \bmod 2^{r+1}.$ Thus, by the induction hypotesis this would mean that $k\in \bigcup\limits_{r=1}^{n} V_r$ but we also have that $k\in V_{r+1}.$ This is an absurd since the funcion is injective. Therefore, the induction proof is compelte.
Now, let us assume that there is $k=2n+1$ such that $k\not \in \bigcup\limits_{r=1}^{\infty} V_r,$ according the the previous proof we must have $V_{r}=2^{r+1}\mathbb{N}+k+2^{r}$ for all sufficiently large $r$. Let us now choose $r$ such that $4k+1<2^{r+3}$ we would have \begin{align} V_{r+2}&=4V_r+1 \\ \iff 2^{r+3}\mathbb{N}+k+2^{r+2}&= 2^{r+3}\mathbb{N}+4k+2^{r+2}+1\\ \iff k&\equiv 4k+1\bmod{2^{r+3}} \end{align} which is impossible by the choice of $r$.