# Proving an Injection

How can I prove an injection between set of natural numbers $$\mathbb{N}$$ and the set of binary numbers $$B=\{2^{i_{1}},2^{i_{2}},...,2^{i_{k}}\}$$ such that :

$$B\xrightarrow{\xi_{s} : \sum_{s=1}^{k}2^{i_{s}}}\mathbb{N}$$

That is for some $$n\in\mathbb{N}$$ there exists a unique binary number representation for $$n$$ such that : $$n=2^{i_{1}}+2^{i_{2}}+...+2^{i_{k}}$$

Side Note: This is part of my analysis assignment which is asking me to show that the binary representation of a natural number is unique I wish that no one writes me a proof but rather give me a hint on how to think/approach this proof based on my choice of proving an injectivity of the sets above.

• As requested, a hint: if two subsets are the binary integers are different, there must be a biggest binary integer that they disagree at. What does this say about the size of the sum? This is using the following characterization of injectivity: a function $f$ is injective iff $x \neq y \implies f(x) \neq f(y)$. – Duncan Ramage Sep 23 at 20:36
• I suggest induction. Let $n$ be the least natural number which can be written in two distinct ways as the sum of distinct powers of $2$. Derive a contradiction. – lulu Sep 23 at 20:37
• I believe I have understood your point when you said there must be a biggest binary integer they disagree at. Then I must consider the two possible cases concerning the sizes of these sums and derive a contradiction right? – WiWo Sep 23 at 20:44

Suppose two binary expansions of length at least $$n$$ have equal value. That is, for some digits of the expansion $$0 \leq a_i, b_i \leq 1$$: $$a_n\cdot2^n + \cdots + a_1\cdot 2^1 + a_0 = b_n\cdot2^n + \cdots + b_1\cdot 2^1 + b_0.$$ We endeavour to prove that $$a_i = b_i$$ for appropriate $$i$$. Take the remainders modulo 2, which leads us to: $$a_n\cdot0 + \cdots + a_1\cdot 0 + a_0 = b_n\cdot0 + \cdots + b_1\cdot 0 + b_0; \\ a_0 = b_0.$$ So $$a_0 = b_0$$, and therefore: $$a_n\cdot2^{n-1} + \cdots + a_1\cdot 2^0 = b_n\cdot2^{n-1} + \cdots + b_1\cdot 2^0.$$ This itself is an equality of binary expansions, so we may proceed by induction to prove this for any $$n$$ and show the desired result. I will leave the precise details of this induction to you. The end result is that $$a_i = b_i$$ for $$0 \leq i \leq n$$, which is to say that the binary expansion is unique.
Suppose that $$A = \{a_1, a_2, \cdots, a_n\}$$ and $$B = \{b_1, b_2, \cdots, b_n\}$$ have the same binary value, that is $$\sum{2^{a_i}} = \sum{2^{b_i}}$$.
Suppose for contradiction that these sets are not equal. Then certainly there is a largest exponent that occurs in one that does not occur in the other. Without loss of generality, suppose this exponent is $$a_x \in A$$. Then certainly: $$\sum_{i}{2^{a_i}} = \sum_{a_i < a_x}{2^{a_i}} + 2^{a_x} + \sum_{a_i>a_x}{2^{a_i}}, \text{and} \\ \sum_{i}{2^{b_i}} = \sum_{b_ia_x}{2^{b_i}}.$$ Recall that $$a_x$$ was the largest exponent not shared by both, so since they are equal we may cancel the larger sum, obtaining: $$2^{a_x} = \sum_{b_i < a_x}{2^{b_i}} - \sum_{a_i < a_x}{2^{a_i}}.$$ The right hand side of this equality is at most the sum of all powers of two less than $$a_x$$, so: $$2^{a_x} \leq \sum_{i=0}^{a_x-1}{2^i} = 2^{a_x} - 1.$$ And this is a contradiction. Hence the sets are equal.