# Summing elements of a sequence

Let the sequence $a_n$ be defined as $a_n = 2^n$ where $n = 0, 1, 2, \ldots$

That is, the sequence is $1, 2, 4, 8, \ldots$

Now assume I am told that a certain number is obtained by taking some of the numbers in the above sequence and adding them together (e.g. $a_4 + a_{19} + a_5$), I may be able to work out what numbers from the sequence were used to arrive at the number. For example, if the number given is 8, I know that the sum was simply $a_3$, since this is the only way to get 8. If i'm told the number is 12, I know that the sum was simply $a_3 + a_2$.

If I'm told what the resulting number, can you prove that I can always determine which elements of the above sequence were used in the sum to arrive at that number?

-

Fundamental reason: The division algorithm.

For any number $a\geq 0$, we know there exists a unique $q_0\geq 0$ and $0\leq r_0<2$ such that $$a=2q_0+r_0.$$ Similarly, we know there exists a unique $q_1\geq 0$ and $0\leq r_1<2$ such that $$q_0=2q_1+r_1.$$ We can define the sequences $q_0,q_1,\ldots$ and $r_0,r_1,\ldots$ in this way, i.e. $q_{n+1}\geq 0$ and $0\leq r_{n+1}< 2$ are the unique solutions to $$q_n=2q_{n+1}+r_{n+1}.$$ Note that $0\leq r_n<2$ is just equivalent to $r_n\in\{0,1\}$.

Also note that if $q_n=0$ for some $n$, then $q_k=0$ and $r_k=0$ for all $k>n$.

Because $\frac{1}{2} q_n\geq q_{n+1}$ for any $n$, and because every $q_n$ is a non-negative integer, we will eventually have $q_n=0$ for some $n$. Let $N$ be the smallest index such that $q_N=0$.

Then \begin{align} a&=2q_0+r_0\\ &=2(2q_1+r_1)+r_0\\ &\cdots\\ &=2(2(\cdots (2q_N+r_N)+r_{N-1}\cdots )+r_1)+r_0\\ &=2^Nr_N+2^{N-1}r_{N-1}+\cdots+r_0\\ \end{align} is a sum of terms from the sequence $a_n=2^n$, specifically those $a_n$'s for which the corresponding $r_n=1$ instead of 0.

-

Yes, you can: this long question is just a fancy way to ask you to "prove" that any natural number can be written in base 2.

This is always possible to do at any base $\,1<n\in\Bbb N\,$ , as (many?... most?...some?) of us learned in high school.

-

Given a number $a$, we can write it as $$a = \sum_{k=0}^n a_n 2^n$$ where $a_n \in \{0,1\}$. Essentially, for any number we can write it in a binary representation. Hence, given a number $a$, you can uniquely identify the $k$'s such that $a_k$'s are non-zero. Hence, $$a = \sum_{k \in \{m: a_m \neq 0\}} 2^k$$

EDIT

We will proceed by induction to show that every positive integer can be expressed as $\displaystyle \sum_{k=0}^{n} a_k 2^k$, where $a_k \in \{0,1\}$ in a unique manner.

Clearly, $1 = 1 \cdot 2^0$. Further this is the unique representation since $2^k \geq 2$ for all $k \geq 1$. Hence, if there exists a non-zero $a_j$ for some $j\geq1$, then $$1 = \sum_{k=0}^n a_k 2^k \geq a_j 2^j = 2^j \geq 2 > 1$$ Hence, not possible. Hence, $1$ can be uniquely expressed as $\displaystyle \sum_{k=0}^n a_k 2^k$.

Assume that all $m \leq a$ has a unique binary representation i.e. $$m = \displaystyle \sum_{k_m=0}^{n_m} a_{k_m}2^{k_m}$$

Now we need to prove that $a+1$ has a unique binary representation. Let $$n_{a+1} = \max \{2^n \leq a+1: n \in \mathbb{N}\}$$ Now consider $b = a +1 - 2^{n_{a+1}}$. By induction hypothesis, we have a binary representation for $b$ as $\displaystyle \sum_{k_b=0}^{n_b} a_{k_b} 2^{k_b}$. Now the claim is that $n_b < n_{a+1}$. (Why? Else this will contradict the maximality of $n_{a+1}$. This can be proved by making use of the fact that $2^s + 2^s = 2^{s+1}$. You should also be able to show that the representation is in fact the unique representation.) Hence, this proves the unique binary representation for any positive integer.

-

Basically the problem asks you in a fancy way to prove that any number $n \geq 1$ can be written uniquely as the sum of distinct powers of $2$.

Existence: Strong Induction. $P(1)$ is obvious, while for the inductive step pick some $m$ so that

$$2^m \leq n < 2^{m+1} \,.$$

If $n=2^m$ you are done, otherwise $n=2^m+(n-2^m)$ and you can use the inductive step on $n-2^m$. Note that $n-2^m<2^m$, which guarantees that the powers of two are distinct.

Uniqueness:

Assume that $a_1 < a_2 < .. <a_n$ and $b_1 < b_2 < .. < b_m$ are such that

$$\sum 2^{a_i} = \sum 2^{b_j} \,.$$

Then

$$2^{a_1} ( 1+ 2^{a_2-a_1} +...+ 2^{a_n-a_1})= 2^{b_1} ( 1+ 2^{b_2-b_1} +...+ 2^{b_m-b_1})$$

Fundamental Theorem of Arithmetic tells us that the power of two in this must be $2^{a_1}=2^{b_1}$. Thus from here we get $a_1=b_1$ and

$$2^{a_2} +...+ 2^{a_n}= 2^{b_2} +...+ 2^{b_m} \,.$$

Repeat and you are done. You can probably simplify the argument a lot if you use contradiction, and cancel all the powers of two which appear on both sides.

-

A result which is (or should be) well-known and which I proved many years ago as an undergraduate is this:

Suppose $(b_i)_{i=0}^{\infty}$ is an strictly increasing series of integers with $b_0 = 1$ called the bases. Usually $b_i = b^i$ where $b \ge 2$ is an integer. Then every positive integer $n$ can be represented in the form $\sum_{i=0}^{M(n)} a_i b_i$ where $M(n)+1$ is the number of "digits" in the representation of $n$ in the "base" $(b_i)_{i=0}^{\infty}$, the $a_i$ are integers and $0 \le a_i < b_{i+1}/b_i$; the representation is unique for all integers if and only if $b_{i+1}/b_i$ is an integer for all $i$.

This shows why the usual binary, ternary, ..., decimal representations, where $b_i = b^i$ for an integer $b$, are unique. It also shows that the "factorial" representation, where $b_i = (i+1)!$ is unique.