Hello,
I need to show that is a bijection of on
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?
Thanks in advance.
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?
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.
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.