Prove that every positive integer is uniquely expressible in the form $$2^{j_0} + 2^{j_1}+ 2^{j_2} + \cdots + 2^{j_m}$$ where $m \geq 0$ and $0 \leq j_0 < j_1 < j_2 < \cdots < j_m$.

\newcommand{\Z}{\mathbb{Z}} \newcommand{\N}{\mathbb{N}} \begin{proof} This is the usual binary representation of a positive integer. $\bullet$ We reason by induction to prove the existence of such a representation. First $1 = 2^0 = \sum_{j \in A} 2^j$, where $A = \{0\}$. Now let $n>1$ be any integer, and assume that every positive integer $k<n$ is expressible in the form $2^{j_0} + 2^{j_1}+ 2^{j_2} + \cdots + 2^{j_m}$ where $m \geq 0$ and $0 \leq j_0 < j_1 < j_2 < \cdots < j_m$. In others words, if we denote $\mathscr{P}_f(\N)$ the set of finite subsets of $\N$, we assume $P(n)$, where $$P(n) \iff \forall k \in [\![1, n]\!] ,\ \exists A_k \in \mathscr{P}_f(\N) \setminus \{\varnothing\} ,\ k = \sum_{j \in A_k} 2^j.$$ (If we take $A_k \in \mathscr{P}_f(\N)$, $0$ is represented.) We prove that $n$ itself is so represented. The division of $n$ by $2$ gives $$n = 2 m + r, \qquad r\in \{0,1\}.$$ Then $0< m \leq n/2 < n$, so that we may apply the induction hypothesis to $m$: $$m = \sum_{j \in A_m} 2^j,$$ for some non empty finite set $A_m \subset \N$. Then $$n =r + 2 \sum_{j \in A_m} 2^j = r + \sum_{j \in A_m} 2^{j+1} = r + \sum_{k \in B_m} 2^{k},$$ where $B_m = \{k \in \N \mid k-1 \in A_m\}$. Note that $B_m \subset \N\setminus \{0\}$. Now define $A_n = B_m$ if $r = 0$, and $A_n = B_m \cup \{0\}$ if $r = 1$. Then $$n = \sum_{j \in A_n} 2^j.$$ This proves $P(n+1)$, and the induction is done. Therefore every positive integer $n$ is of the form $$n = \sum_{j \in A} 2^j$$ for some non empty subset $A \subset \N$. If $A = \{j_0,j_1,\ldots,j_m\}$, $$n = 2^{j_0} + 2^{j_1} + 2^{j_2} + \cdots + 2^{j_m},\qquad 0 \leq j_0 < j_1< \cdots < j_m,\qquad m \geq 0.$$ $\bullet$ Now we prove the unicity of such a representation. Suppose that $$n = \sum_{j \in A} 2^j = \sum_{j \in B} 2^j,$$ where $A,B$ are non empty finite subsets of $\N$. if $A = \{j_1, j_2,\ldots,j_m\}$ and $B = \{k_1, k_2,\ldots, k_l\}$, this gives $$n = 2^{j_0} + 2^{j_1} + 2^{j_2} + \cdots + 2^{j_m} = 2^{k_0} + 2^{k_1} + 2^{j_2} + \cdots + 2^{k_l},$$ where $m \geq 0,\ 0 \leq j_0 < j_1 < j_2 < \cdots < j_m$ and $l \geq 0, \ 0 \leq k_0 < k_1 < j_2 < \cdots < k_l$. Without loss of generality, we may suppose that $m \leq l$. Assume, for the sake of contradiction, that there is some $i \in [\![0, m]\!]$ such that $j_i \ne k_i$, and let $I$ be the first index for which $j_I \ne k_I$. Then $$2^{j_I} + \cdots + 2^{j_m} = 2^{k_I} + \cdots + 2^{k_l}.$$ If $j_I k _I $. Therefore $j_0 = k_0, j_1 = k_1, \ldots, j_m = k_m$. If $m < l$, we obtain after simplification $0 < 2^{k_m + 1} + \cdots + 2^{k_l} = 0$: this is absurd, so $m = l$ and $A = B$. The two representations are identical. \end{proof}

Homepage › Solution manuals › Ivan Niven › An Introduction to the Theory of Numbers › Exercise 1.2.44 (Binary decomposition of positive integers)

An Introduction to the Theory of Numbers

Exercise 1.2.44 (Binary decomposition of positive integers)

Prove that every positive integer is uniquely expressible in the form

2^{j_{0}} + 2^{j_{1}} + 2^{j_{2}} + \dots + 2^{j_{m}}

where $m \geq 0$ and $0 \leq j_{0} < j_{1} < j_{2} < \dots < j_{m}$ .

Answers

Proof. This is the usual binary representation of a positive integer.

$∙$ We reason by induction to prove the existence of such a representation.

First $1 = 2^{0} = \sum_{j \in A} 2^{j}$ , where $A = {0}$ .

Now let $n > 1$ be any integer, and assume that every positive integer $k < n$ is expressible in the form $2^{j_{0}} + 2^{j_{1}} + 2^{j_{2}} + \dots + 2^{j_{m}}$ where $m \geq 0$ and $0 \leq j_{0} < j_{1} < j_{2} < \dots < j_{m}$ . In others words, if we denote $𝒫_{f} (ℕ)$ the set of finite subsets of $ℕ$ , we assume $P (n)$ , where

P (n) ⟺ \forall k \in [[1, n]], \exists A_{k} \in 𝒫_{f} (ℕ) ∖ {\emptyset}, k = \sum_{j \in A_{k}} 2^{j} .

(If we take $A_{k} \in 𝒫_{f} (ℕ)$ , $0$ is represented.)

We prove that $n$ itself is so represented. The division of $n$ by $2$ gives

n = 2 m + r, r \in {0, 1} .

Then $0 < m \leq n ∕ 2 < n$ , so that we may apply the induction hypothesis to $m$ :

m = \sum_{j \in A_{m}} 2^{j},

for some non empty finite set $A_{m} \subset ℕ$ . Then

n = r + 2 \sum_{j \in A_{m}} 2^{j} = r + \sum_{j \in A_{m}} 2^{j + 1} = r + \sum_{k \in B_{m}} 2^{k},

where $B_{m} = {k \in ℕ ∣ k - 1 \in A_{m}}$ . Note that $B_{m} \subset ℕ ∖ {0}$ .

Now define $A_{n} = B_{m}$ if $r = 0$ , and $A_{n} = B_{m} \cup {0}$ if $r = 1$ . Then

n = \sum_{j \in A_{n}} 2^{j} .

This proves $P (n + 1)$ , and the induction is done. Therefore every positive integer $n$ is of the form

n = \sum_{j \in A} 2^{j}

for some non empty subset $A \subset ℕ$ . If $A = {j_{0}, j_{1}, \dots, j_{m}}$ ,

n = 2^{j_{0}} + 2^{j_{1}} + 2^{j_{2}} + \dots + 2^{j_{m}}, 0 \leq j_{0} < j_{1} < \dots < j_{m}, m \geq 0 .

$∙$ Now we prove the unicity of such a representation. Suppose that

n = \sum_{j \in A} 2^{j} = \sum_{j \in B} 2^{j},

where $A, B$ are non empty finite subsets of $ℕ$ . if $A = {j_{1}, j_{2}, \dots, j_{m}}$ and $B = {k_{1}, k_{2}, \dots, k_{l}}$ , this gives

n = 2^{j_{0}} + 2^{j_{1}} + 2^{j_{2}} + \dots + 2^{j_{m}} = 2^{k_{0}} + 2^{k_{1}} + 2^{j_{2}} + \dots + 2^{k_{l}},

where $m \geq 0, 0 \leq j_{0} < j_{1} < j_{2} < \dots < j_{m}$ and $l \geq 0, 0 \leq k_{0} < k_{1} < j_{2} < \dots < k_{l}$ .

Without loss of generality, we may suppose that $m \leq l$ . Assume, for the sake of contradiction, that there is some $i \in [[0, m]]$ such that $j_{i} \neq k_{i}$ , and let $I$ be the first index for which $j_{I} \neq k_{I}$ . Then

2^{j_{I}} + \dots + 2^{j_{m}} = 2^{k_{I}} + \dots + 2^{k_{l}} .

If $j_{I} < k_{I}$ , then all terms except $2^{j_{I}}$ are divisible by $2^{j_{I} + 1}$ , so that $2^{j_{I} + 1} ∣ 2^{j_{I}}$ , and $2 ∣ 1$ . This is a contradiction, and we obtain a similar contradiction if $j_{I} > k_{I}$ . Therefore $j_{0} = k_{0}, j_{1} = k_{1}, \dots, j_{m} = k_{m}$ . If $m < l$ , we obtain after simplification $0 < 2^{k_{m} + 1} + \dots + 2^{k_{l}} = 0$ : this is absurd, so $m = l$ and $A = B$ . The two representations are identical. □

richardganaye

2024-10-02 09:42

Comments

Hi Richard, if you want me to delete the comments once the erratas have been discovered, let me know or you can do it yourself to make the final draft without comments. Glad to help. I will work through them all, but I will work slowly. Today I noticed here that the set A=\{j_{1}..etc\} should begin with subscript 0. Same with set B. Also after the phrase "after simplification" the subscript should be k_{m+1} instead of k_{m}+1.

BretSherfinski • 2025-02-27
Hi Bret. Errors corrected. I don't see any point in destroying the comments: they are part of the history of each exercise. Even if I am a little ashamed of the remaining errors, I know that even a careful rereading on my part would not be enough: I had reread this solution without seeing anything! I regretted until now the lack of reactions to these solutions, and I am happy that an exchange is taking place through these comments. I myself had made some remarks to solutions of other people on this site, unfortunately often remaining unanswered. I will remain attentive to all your suggestions, and I will respond to them regularly. Thank you.

richardganaye • 2025-03-03

Exercise 1.2.44 (Binary decomposition of positive integers)

Answers

Comments

Add answer