# Prove a function in 2 variables is onto

Consider the function $h: N \times N \rightarrow N$ so that $h(a,b) = (2a +1)2^b - 1$, where $N=\{0,1,2,3,\dots\}$ is the set of natural numbers.

Prove that it is onto.

Tried taking various examples and value putting technique to see that most of values in the range are covered, which supports my intuition that the function is onto. \begin{array}{cc|c} a & b & h(a,b) \\\hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 2 \\ 0 & 2 & 3 \\ 2 & 0 & 4 \\ 1 & 1 & 5 \\ \vdots&\vdots & \vdots \end{array}

• You could show it is bijective, by giving an explicit inverse, e.g. $b$ is the number of powers of $2$ dividing $c+1$ and $a=\dfrac{(c+1)/2^b - 1}{2}$. If h(h^{-1}(c))=c and $h^{-1}(h(a,b))=(a,b)$ then $h$ is onto (and 1-to-1) Oct 16, 2015 at 9:18
• It will b much more obvious that $2^a(2b+1)$ is ontp the positive integers, For any positive integer can be expressed (uniquely, but we don't need that for onto) as a power of $2$ times an odd number. Oct 16, 2015 at 9:21

Hint: for any $n = h(a,b)$ for unknown $a,b$, express $n+1$ in binary. Can you now see an obvious candidate for $b$ and deduce $a$?
Consider a natural number $n$ and let's prove that it is of the given form.
$$(2a+1)2^b = n+1$$
$n+1$ can be expressed as $2m$ or $2m+1$ for some $m$. In the first case, you can repeat the procedure with m, obtaining that $m=2^k$ for some $k$ or $m=2^j h$ where $h$ is of the form $2l + 1$.
So, in the end, you get that you can express $n+1$ as a number of the given form $\forall n \in \mathbb{N}$.