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}$).
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.)
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$.