Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

5 Answers

up vote 1 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.