Trying to show that the function $f: \mathbb{N}^2 \to \mathbb{N}$ defined by $f(m,n) = 2^m (2n+1) - 1$ is surjective. Easy to show that any even $k \in \mathbb{N}$ can be mapped to by taking $(m,n) = (0, k/2)$. Not so sure about odd $k$, even by induction. Would appreciate any pointers.
Edit: I should add, without using the fundamental theorem of arithmetic, only in fairly introductory set theoretic terms (say level of Jech, chapter on finite sets).
On
If $k\in\mathbb N$, then let $2^m$ be the highest power of $2$ that divides $k+1$. Then $\frac{k+1}{2^m}$ is odd; in other words, it is of the form $2n+1$. Therefore, $f(m,n)=k$.
On
The same idea, but a bit different angle:
every natural number $k+1$ can be written in a binary system. For example, let $k+1 = 1101\dots0100$, which means $$ k+1 = 1\times 2^n + 1\times 2^{n-1} + 0\times 2^{n-2} + \cdots + 0. $$ Let's remove all zeroes from consideration, i.e. let $\alpha_1>\alpha_2>\dots$ and $$ k+1 = 2^{\alpha_1} + 2^{\alpha_2} + \dots + 2^{\alpha_s}. $$ Note that all $\alpha$ differ at least by $1$. Now write the last equality as $$ k+1 = 2^{\alpha_s} \left( 2 \underbrace{\left( 2^{\alpha_1-\alpha_s-1}+\dots+2^{\alpha_{s-1}-\alpha_{s}-1} \right)}_{n} + 1 \right). $$ Interestingly $$ 2^{\alpha_s + 1} - 1 = k \text{ xor } (k+1). $$
For odd $k$, you have
$$2^m(2n + 1) - 1 = k \implies 2^m(2n + 1) = k + 1 \tag{1}\label{eq1A}$$
Note $k + 1$ is even, so it has a highest power of $2$ divisor, call it $m$, as well as an odd factor. Have this odd factor be $2n + 1$ for some $n \ge 0$. Note this only works properly if you assume that $0 \in \mathbb{N}$.