1,631 views

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.

1. Prove that the function $h$ is an injection (one-one).
2. Prove that it is also a Surjection (onto)

can any body proof the onto part

any idea..

@Verma Ashish

I think proving one-one is very easy directly from the definition.

Let's prove its surjective.

$\underline{\mathbf{Proof \;for\; Surjection\; (onto):}}$

$3$ steps followed in induction:

1. Prove for $\mathbf {n = 1}$
2. Assume its true for $\mathbf{k+1}$
3. Then, prove it for $\mathbf{n}$

Let us prove first that any positive number can be written in the form $\mathbf{2^a(2b+1)}$, where $\mathbf{a, b \in non-negative\ integers}$

It is true for $\mathbf{n = 1} \text{(Substitute a = 0, b = 0)}$

Now, let's suppose its true of all $\mathbf {k < n}$,

$\therefore$ we need to prove that its true for $\mathbf n$.

When $\mathbf {n \in odd}$, let $\mathbf{2b+1}$. Then we can assume $\mathbf{a = 0}$

when $\mathbf{ n \in Even, \;\text{let} \;n = 2m}$

Then by using induction conjecture, there should exist natural numbers $\mathbf {a_1}$ and $\mathbf b$ so that $\mathbf{m = 2^{a_1}(2b+1)}$

Then $\mathbf{n = 2^a(2b+1)}$, where $\mathrm {a = a_1+1}$

Hence, proved.

Thanks, @jeet

I proved one-one by basic definition..(in answer)

### Subscribe to GO Classes for GATE CSE 2022

The given function is $h(a,b)=(2a+1)2^b-1$

$h:N\times N\to N$

(i) injection:-

$h$ will be one-to-one if, $h(a,b)=h(c,d)\implies (a,b)=(c,d)$

$h(a,b)=h(c,d)$

$\Rightarrow (2a+1)2^b-1=(2c+1)2^d-1$

$\Rightarrow \frac{2a+1}{2c+1}=2^{d-b}$

If $d\neq b$ then RHS will always be even, but LHS is (odd/odd) which is odd.

$\text{LHS} = \text{RHS} \text{ only if }d=b,$

$\Rightarrow \frac{(2a+1)}{(2c+1)}=1$

$\Rightarrow (2a+1)=(2c+1)\Rightarrow a=c$

$\implies (a,b)=(c,d),\; hence\; h$ is one-one.

(ii) Surjection:-

For $h$ to be onto, there should not be any non-negative integer which can't be generated by the function. i.e. all the elements of co-domain should be mapped by some element of domain set.

Now look at the function it is $(2a+1)2^b-1$

If $b=0, (2a+1)2^b-1=2a \implies$ all non-negative even numbers generated.

If $b\neq 0,(2a+1)2^b-1\implies$ all non-negative odd numbers generated.

So, all the numbers of co-domain (i.e. $N$) are mapped by some $(a,b)$ pair. Hence, h is onto (surjective).

edited by

For the below part, I understand the outcome would be odd always. Though how can it be concluded that all the odd numbers would be generated?

If $b≠0,(2a+1)2^b−1$ ⟹ all non-negative odd numbers generated.

Any odd number can be written in $(2a+1)2^b-1$ form.

Ex:-(i) 35,  $(2a+1)2^b-1=35$

$\implies (2a+1)2^b=36\implies 9\times 2^2(a=4,b=2)$

(ii) $87=(2a+1)2^b-1$

$\implies (2a+1)2^b=88\implies 11\times 2^3(a=5,b=3)$
In general,

$(2a+1)2^b-1=odd$

$(2a+1)2^b=even(\geq 2)$

And this even number can be represented as $odd\times 2^x$, uniquely.
These are two examples, it doesn't prove the statement that every odd number can be generated by $(2a+1)2^b−1$
Yup this makes sense!
Yes.. 2 examples can't prove it..

I have also given general idea in 2nd comment..
JEET's comment also makes sense that if every positive integer can be generated by $\mathbf{n = 2^a(2b+1)}$,then every non negative integer will be generated by $\mathbf{n = 2^a(2b+1)-1}$

@Verma Ashish Thanks for the awesome answer!

Nice answer but I felt few points to be highlighted [for my understanding only].

$(I)$ what is (odd/odd)==odd?

We get a situation as:

$$\frac{2a+1}{2c+1}=2^{d-b}$$

Now if $d>b$ [let $k=d-b$] then this equation looks like:

$$\frac{2a+1}{2c+1}=2^k \implies 2a+1=2^k(2c+1) \tag 1$$

In $(1)$ the RHS is an even number since $k>1$ while LHS is odd, which is not possible.

Now if $b>d$ [let $l=b-d$] then this equation looks like:

$$\frac{2c+1}{2a+1}=2^l \implies 2c+1=2^k(2a+1) \tag 2$$

In $(2)$ the RHS is an even number since $l>1$ while LHS is odd, which is not possible.

So $d\neq b$ is not possible.

$(II)$ if $b\neq 0$ then all non negative odd numbers can be generated by $(2a+1)2^b-1$. How?

The general term for the odd number sequence is $2k-1$ , $k=1,2,3...$

If $k$ is odd then $(2a+1)2^b-1$ will generate it by using $b=1$ and $a=0,1,2,3...$

If $k$ is even, then it shall be of the form $2^\alpha * \lambda$ , where $\alpha$ is any integer and $\lambda$ is odd. Then $(2a+1)2^b-1$ generate such odds, using $2a+1=\lambda$ and $b=\alpha+1$

To prove h is one-one we need to basically prove that h cant be same for any two binary pairs i pick,

thus, more formally For h being one-one. h(a,b)=h(c,d) => (a,b)=(c,d)

So we will prove the contrapositive of it i.e. (a,b) != (c,d) => h(a,b) !=h(c,d)

Now lets pick h(a,b)=(2a+1)2^b -1 and h(c,d)=(2c+1)2^d -1

For comparing the above i ignore ‘-1’ coz any ways its just the gap within them! (even if you dont ignore not much of an issue coz if those two numbers turn out to be same then one doing a ‘-1’ still they would be same and if they were initially different then doing a ‘-1’ wont change the gap between them)

So lets analyse this h function in binary..as it would be easier to prove i feel.

h(a,b)=(2a+1)*2^b  [ignore -1]

which basically means take the binary equivalent of a => left shif by 1 bit (indicated by 2*a) =>and then add 1 to it (means make it odd or equivalently saying make its LSB bit as 1)=> and then left shift the whole previous setting of bits by ‘b’ bits to left (indicated by a multiplication of 2^b)

So my claim is after doing all this ill get

a number in which ‘b’ lsb bits are zero and then b+1 st bit is guaranteed to be 1

Now remember this rule ..i just formulated we will use it to prove for two different binary pairs h cant be same.

so lets pick up c,d=> h(c,d)=(2c+1)2^d

NOW,

Okay so lets begin the comparison,

For 2 binary pairs to differ atleast one of the element of the tuple should be different,

Case 1: For (a,b) and (c,d) assume a=c but b!=d

This case is easy,

by the above interpretation its clear that the ‘b’ in (a,b) represents a ‘b’ bit left shift after which b+1 st bit is guranteed to be 1 (..as 2a+1 is defintely “odd”)

So if b!=d that means they differ by atleast 1.

So say b<d (as they differ so either would be smaller than the other)

thus doing a left shift by ‘b’ (say b=3) bits makes b+1 st bit as 1 (=> 3rd bit =0 and 4th bit in binary is 1)

and doing a left shift by ‘d’ (say d=4) bits makes d+1 st bit as 1 (=>4th bit =0 and 5th bit in binary is 1)

Thus as per the highlighted part in this case we can conclude here itself that h(a,b) and h(c,d) can’t be same.

Now also due to this it even doesnt matter what ‘a’ and ‘c’ actually was now they might be same or might be different doesnt matter, we actually proved just on the basis of ‘b’ and ‘d’ that they differ altogether.

Case 2: For (a,b) and (c,d) assume a!=c and b!=d

I think i need not to prove this, as if you follow till here then its clear that if ‘b’ and ‘d’ differ then (a,b) and (c,d) never be same irrespective of whatever ‘a’(=>more precisely 2a+1) and ‘c’(more precisely 2c+1)  are…

Case 3: For (a,b) and (c,d) assume a!=c and b=d

This is the last case by which they can differ !

Now again its also easy to prove why they differ here too!

as ‘b’ and ‘d’ are same thus both have b+1 st bit as 1 (or can also be called as d+1 st bit)

and then post that we have binary of ‘a’ and ‘c’  (more precisely binary of 2a+1 and 2c+1 ), as we know they arent same => so is there binary wont be same

hence even in this case if the two tuples are different then h cannot evaluate as same proved.

THUS USING THE CONTRAPOSITIVE STATEMENT ITS CLEAR TO SAY THAT IF h EVALUATES SAME FOR TWO BINARY PAIRS THEN THOSE BINARY PAIRS HAVE TO BE SAME !

Thus we got an injection here!

Now proving that this function is ONTO is not a big deal,

So lets do some ‘setting’,

let b=0 for h(a,b)

we get,

h(a,0) = (2a+1)*2^b – 1 = (2a+1) – 1 = 2a

enumerating over a as {0,1,2,3...} generated whole of the “EVEN NUMBER SPACE”

ITS EASY TILL HERE..

NOW COMES THE INTERESTING CASE ..To prove “h” also “SPANS” whole of the ODD number space! ,

Lets say it doesnt SPAN whole of the ODD number space (for any setting of a and b)

then definitely there should exists atleast one odd number who cant be expressed as (2a+1)2^b-1

so,

(2a+1)*2^b – 1 != k  (let k be that odd number)

(2a+1)*2^b != k+1 ==> NOW bcoz k is ODD , k+1 is definitely EVEN

THUS,

(2a+1) !=  (k + 1) / 2^b

Now as we know k+1 is EVEN = > (since k is chosen to be ODD)

THINK OF ‘k+1’ LIKE A BAG whose NET WORTH IS EVEN so DEFINITELY IT SHOULD CONTAIN SOME NUMBER OF 2’s IN IT STUFFED !

Let that ‘ some number of 2’s ’ be ‘m’

SO k+1 contains 2^m as a factor inside it.

Now as we divide it by 2^b, lets ‘raise’ b to m so that 2^b=2^m

and Now perform the division of k+1/2^b=k+1/2^m

So this would remove off all 2’s in k+1 (or in a way throw out all 2’s from the bag named k+1)

Thus,

what we would eventually left off would be a PURE ODD NUMBER, lets call it as ‘an_odd’

Thus we obtain,

(2a+1) != an_odd

Now RHS is an ODD number (we did its ‘setting' just now!)

and its easy to see that why LHS is ODD (more precisely 2a+1 is basically the way how odd numbers are defined ..more simply...on division by 2 giving a remainder of 1=>2(a)+1)

But we started off by claiming that LHS != RHS

which seems to be a false claim!

Thus LHS has to be equal to RHS thus,

WE PROVED THAT THERE CANNOT BE ANY ODD NUMBER, WHO CAN POSSIBLY BE DEPRIVED OF NOT BEING ABLE TO EXPRESSED BY THE GIVEN DEFINITION OF h(a,b).

Thus we proved that h is ALSO ONTO

SO,

h being ONE-ONE + ONTO => h is BIJECTIVE.

for every  value of (a,b) there exist value in co-domain set which makes it an onto  function here
by

which makes co-domain = range here hence onto
Actually we need to prove it is a bijection or not, right?

@Kaluti is there any proof for this?

for every value of (a,b) there exist value in co-domain set

This statement neither implies one - one nor onto..

h:N×N→N

function  h(a,b)=(2a+1)2b−1h(a,b)=(2a+1)2b−1,

(0,0)= 0

(0,1)=1

(0,2)=3 ... we can see every time function output is unique

(1,0)=2 ... output unique .. so every function is one to one

and every co-domain image in domain so function also onto

by