3
$\begingroup$

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}

$\endgroup$
2
  • $\begingroup$ 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) $\endgroup$
    – Henry
    Oct 16, 2015 at 9:18
  • $\begingroup$ 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. $\endgroup$
    – André Nicolas
    Oct 16, 2015 at 9:21

2 Answers 2

Reset to default
2
$\begingroup$

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$?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .