# Bijection question

• Oct 6th 2013, 05:36 AM
peter89
Bijection question
Hello,

I need to show that $\displaystyle (m,n) \mapsto 2^{m-1}(2n-1)$ is a bijection of $\displaystyle \mathbb{N} \times \mathbb{N}$ on $\displaystyle \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?

• Oct 6th 2013, 05:51 AM
Plato
Re: Bijection question
Quote:

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

Any positive integer is the product of a power of two times an odd number.
EXAMPLES:
$\displaystyle 21=2^0(2(11)-1),~32=2^5(2(1)-1),~44=2^2(2(6)-1)$.

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

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

Can you finish?
• Oct 6th 2013, 07:08 AM
peter89
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?
• Oct 6th 2013, 07:23 AM
Plato
Re: Bijection question
Quote:

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.
• Oct 6th 2013, 10:17 AM
emakarov
Re: Bijection question
Quote:

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.
• Oct 6th 2013, 11:44 AM
HallsofIvy
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.