2
$\begingroup$

An exercise problem :

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.

(a) Prove that the function $h$ is an injection (one-one).

(b) Prove that it is also a Surjection (onto).

My attempt :

a. Let $h(a,b) = h(c,d) \\ \implies (2a +1)2^b - 1= (2c +1)2^d - 1\\ \implies (2a +1)2^b = (2c +1)2^d $

Now, $2a$ is even and hence $2a+1$ is odd and similarly $2c+1$. So, the only way the products can be same is when $a = c$ and $b=d$, which shows function is one-one.

b. Lets use induction to prove that every natural element is mapped to by $f$.

Base case:

$h(0,0) = 0$ is true.

Now, assume we have $a, b > 0$ for $h(a,b) = n$.

Now, we want to prove we have $c, d$ for $h(c,d) = n+1$

$h(c,d) = (2c+1) 2^d - 1 \\= n + 1 \\=(2a+1) 2^b - 1 + 1 (\because h(a,b) = n) \\ \implies (2c +1) 2^d = (2a+1) 2^b + 1$

The above equality is satisfied if we put $d = 0$ or $b = 0$ (otherwise LHS is even and RHS is odd) which gives $2c+1 = (2a+1) 2^b + 1 \\ \implies c = (2a+1) 2^{b-1}$

Thus we get $c = (2a+1) 2^{b-1}$ and $d = 0$ and our proof is complete.

Can you explain in formal way, please?

$\endgroup$

2 Answers 2

Reset to default
2
+50
$\begingroup$

a) looks good, but I don't think induction is the way to go for b). Take a number $n$, and add $1$ to it. The result $n+1$ is strictly positive, and can therefore be factorized uniquely into the form $k\cdot 2^l$ where $k$ is an odd natural number and $l$ is natural. That means that $k\cdot 2^l - 1 = n$. Can you find a fitting $a$ and $b$ from that?

$\endgroup$
5
  • $\begingroup$ My intention was to prove $a=c$ and $b=d$ from $(2a +1)2^b = (2c +1)2^d \implies a=c$ and $b=d$ , rt ? $\endgroup$
    – Mithlesh Upadhyay
    Commented Oct 28, 2015 at 14:12
  • $\begingroup$ @MithleshUpadhyay You're talking about part a), now, with the injectivity? What you did there was absolutely fine (of course, you could always flesh out the details on why $b$ and $d$ must be equal). I'm talking about the surjectivity. That's where I think you're on the wrong track. $\endgroup$
    – Arthur
    Commented Oct 28, 2015 at 14:14
  • $\begingroup$ Can you explain ? $\endgroup$
    – Mithlesh Upadhyay
    Commented Dec 13, 2015 at 8:00
  • $\begingroup$ @MithleshUpadhyay I thought I explained it in my answer. Well. Take the number $411$, for instance. We want to find an $a$ and a $b$ such that $(2a+1)\cdot 2^b -1 = 411$. Moving the $-1$ to the other side, we get $(2a+1)\cdot 2^b = 412$. Now, $412 = 103\cdot 2^2 = (2\cdot 51 + 1)\cdot 2^2$. This gives us $412 = (2\cdot 51 + 1)\cdot 2^2$, or, subtracting $1$ again, that $411 = (2\cdot 51 + 1)\cdot 2^2 - 1 = h(51, 2)$. There is nothing special about $411$ in this respect, it can be done for any natural number $n$, and that is what I've written in my answer. $\endgroup$
    – Arthur
    Commented Dec 13, 2015 at 8:14
  • $\begingroup$ Thanks for explanation, I got it. $\endgroup$
    – Mithlesh Upadhyay
    Commented Dec 13, 2015 at 9:08
1
$\begingroup$

Unless $b=0$, $h(a,b)$ is odd, so $h$ cover all odd numbers. If $b=0$, $h(a,0)$ is even, so all even are covered. Hence, every natural numbers are covered.

$\endgroup$
0

You must log in to answer this question.

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