Proving that a function is surjective I want to prove that the function $\mathbb{N}_0 \times \mathbb{N}_0 \rightarrow \mathbb{N}_0$ defined as $(x,y) \mapsto 2^x \cdot (2y + 1) - 1$ is bijective. I have already proven that it is injective, but cannot figure out how to prove the surjectivity, since all other examples that I have seen only have 1 variable (i.e. $\mathbb{N} \rightarrow \mathbb{N}$). 
 A: We want to show that there exist $x,y \in \Bbb{N}$ such that $2^x(2y+1)-1 = z.$
This is equivalent to $2^x(2y+1) = z+1$.  Maybe there are better ways, but I would break into cases (at least as a "first draft" proof).


*

*Case I: $z+1$ is odd.  In this case we can choose $y$ so that $2y+1 = z+1$.  Then we end up with $2^x = 1$, and so $x = 0$.

*Case II(a): $z+1$ is a power of 2.  In this case we can choose $x$ so that $2^x = z + 1$.  Then we get $2y+1 = 1$, and so $y = 0$.

*Case II(b): $z+1$ is even but not a power of 2.  This case is left as an exercise to the reader.  (Big hint:  Think about what you get if you divide out sufficiently large powers of 2 from evens that aren't powers of 2, such as 6, 18, 100, 576, etc.)

A: All we need to prove is that there exist such pair $(x,y)\in\mathbb{N}_0\times\mathbb{N}_0$ that $2^x(2y + 1) = n + 1$ for each $n\in\mathbb{N}_0$.
Consider the following function $f: \mathbb{N}_0 \to \mathbb{N}_0\times \mathbb{N}_0$:
$$
f(n) = 
\begin{cases}
(0,\frac{n}{2}), & n\text{ is even}\\
(1,0) + f(\frac{n-1}{2}), & n\text{ is odd}.
\end{cases}
$$
One may see that this function is detrmined for all $n\in \mathbb{N}_0$ and if we put $(x,y) = f(n)$ then 
$$
2^x(2y + 1) = n + 1. \tag1
$$
Indeed, if $n$ is even then $\frac{n}{2}\in\mathbb{N}_0$ and $2^0(2\cdot\frac{n}{2} + 1) = n+1$. If $n$ is odd then $\frac{n-1}{2}\in\mathbb{N}_0$ and if $(x_0,y_0) = f(\frac{n-1}{2})$ then if $\frac{n-1}{2}$ is even
$$
2^{x_0}(2y_0+1) = \frac{n-1}{2}+1 \iff 2^{x_0+1}(2y_0+1) = n+1. 
$$
If $\frac{n-1}{2}$ is odd we may repeat this substitution until we not get even argument of function $f$ (for which equation $(1)$ is already proved). The count of our steps would be always finite because $\frac{n-1}{2} < n$ for all $n \in \mathbb{N}_0$, so we will always decrease argument of $f$. The last thing we have to prove is the $(1)$ holds for $n=1$, which is obvious.
A: In order to show that the given function is surjective, we shall take $n\in \mathbb{N}_{0}$ and show that there exist $x$ and $y$ such that the desired relation holds. We can solve the problem by considering the following cases:
Case $1$: $n$ even : Write $n=2m$ for some $m\geq 0$. Then, clearly, $x=0,~y=m$ is the solution.
Case $2$: $n$ odd: Write $n=2m-1$ for some $m\geq 1$. Then, we have 
\begin{eqnarray}
2^{x}(2y-1)=2m.
\end{eqnarray} 
Let $l$ denote the largest divisor of $2m$ that is also a power of $2$. Then, putting $2^{x}=l$ and solving for $y$ gives the required solution.
Example: Suppose $n=19$. Then, $n=2(10)-1$, and thus $m=10,~2m=20$. The largest divisor of $20$ that is also a power of $2$ is $4$. Thus, $2^{x}=4$ or $x=2$. Solving $4(2y+1)=20$ gives $y=2$.
