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.