1. ## Bijection question

Hello,

I need to show that $(m,n) \mapsto 2^{m-1}(2n-1)$ is a bijection of $\mathbb{N} \times \mathbb{N}$ on $\mathbb{N}$

I think I need to show that the expression is both injective and surjective, but I am not sure how to do that.

Maybe a kind person can help me in some direction?

2. ## Re: Bijection question

Originally Posted by peter89
I need to show that $(m,n) \mapsto 2^{m-1}(2n-1)$ is a bijection of $\mathbb{N} \times \mathbb{N}$ on $\mathbb{N}$.
Any positive integer is the product of a power of two times an odd number.
EXAMPLES:
$21=2^0(2(11)-1),~32=2^5(2(1)-1),~44=2^2(2(6)-1)$.

If
$\\2^n(2m-1)=2^k(2j-1)\\2^{n-k}(2m-1)=(2j-1)$

Because LHS is even and RHS is odd, then $n=k$.

Can you finish?

3. ## Re: Bijection question

Thanks for your reply. I am not quite sure how to show that every natural number is an odd number (possibly 1) times some non-negative integer power of 2. I can see it works by doing some examples, but how I precisely can show it? Hmm, maybe a hint?

4. ## Re: Bijection question

Originally Posted by peter89
I am not quite sure how to show that every natural number is an odd number (possibly 1) times some non-negative integer power of 2.
Frankly, I do not know. It is a basic fact of number theory. You did post this in a number theory forum.

5. ## Re: Bijection question

Originally Posted by peter89
I am not quite sure how to show that every natural number is an odd number (possibly 1) times some non-negative integer power of 2.
This can be shown by strong induction. However, you need to decide what facts you can rely on. You are not going to prove commutativity of addition, right? Similarly, it is somewhat obvious that dividing a positive integer repeatedly by 2 will eventually yield an odd number because with each division the number is getting smaller, and this can't go on forever.

6. ## Re: Bijection question

Definition of "even": a natural number, n is even if and only if n= 2k where k is a natural number.

If N is a natural number, it can be written as N= 2K for some natural number K. If K is odd, you are done- N is "2 to the 1 power" times n odd number. if K is even, K= 2M for some integer M. If M is odd, you are done: N= 2K= 2(2M)= 4M is "2 to the 2 power" times an odd number. If M is even, M= 2J for some integer J. If J is odd....
Note that N> K> M> J... so that will eventually terminate.