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?  
 A: 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.
A: 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.
A: 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: 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.
A: 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.
I did this as an answer instead of a comment because
comments are too limiting.
