I have been studying Hindman's Theorem and looking at Hindman's original proof in "Finite Sums from Sequences Within Cells of a Partition of N." In the paper Hindman considers particular sequences $\{x_n\}_{n=1}^{\infty}$ of natural numbers such that $2^s \vert x_{n+1}$ whenever $2^{s-1} \leq x_n$. He defines a natural map $\tau$ on finite sums $F$ of the $x_n$ by $\tau(\sum_{n \in F} x_n)=\sum_{n \in F} 2^{n-1}$.
He then claims that $x_{n+1} > \sum_{i=1}^n x_i$ for every $n$ for this type of sequence $\{x_n\}_{n=1}^{\infty}$, and that for this reason and because every natural number has a unique binary expansion, we have that $\tau$ is one-to-one and onto. I can't figure out why this should be true, and even then, why it is needed to show that $\tau$ is one-to-one and onto? It seems like $\tau$ being one-to-one and onto just follows from every natural number having a unique binary expansion.
Thank you!
That the natural map is both one-to-one and onto is pretty obvious from the uniqueness of the binary representation, but showing that the natural map is a function at all requires you to prove that all finite sums of the $x_i$s are distinct. With the condition that $x_{n+1} > \sum_{i=1}^n x_i$ is true for all $n \ge 1$, it is easy to see that all finite sums are distinct. Let $F_1$ and $F_2$ be two finite, distinct sets of indices. There exists a largest element $\lambda$ which is one (say $F_1$) and not the other. Then $\sum_{F_1} x_i - \sum_{F_2} x_i \ge x_\lambda - \sum_{i=0}^{\lambda-1} x_i > 0$, showing that all finite sums are distinct.
Hindman's argument that his sequence satisfies the condition that $x_{n+1} > \sum_{i=1}^n x_i$ is true for all $n \ge 1$ basically boils down to the binary representation of the $x_i$s, namely that each $x_i$ has ones in its binary representation only in a range where no other $x_j$ does. It is not hard to formalize this notion, however.
Any natural number $x$ can be written uniquely as $x = 2^{s}(2^{t}+\delta)$, where $2^s$ is the largest power of $2$ dividing $x$, and $2^t$ the largest power of $2$ less than or equal to the largest odd factor of $x$, whence $0 \le t$ and $0 \le \delta < 2^{t}$ with $\delta$ odd or $0$. With this notation, it is easy to see that $$\begin{eqnarray*}x&\le&2^{s}(2^t+2^t-1)\\&\le&(2^{s+t+1}-1) - (2^s-1)\\&\le&\displaystyle\sum_{j=0}^{s+t} 2^j - \displaystyle\sum_{j=0}^{s-1} 2^j\\&\le&\displaystyle\sum_{j=s}^{s+t} 2^j\end{eqnarray*}$$
Now use this representation in Hindman's sequence $\{x_i\}_{i=0}^\infty$, so that $x_i = 2^{s_i}(2^{t_i}+\delta_i)$. The conditions on the $x_i$s show that $s_{i+1} > s_i+t_i$ for all $i \ge 1$.
To show that the condition $x_{n+1} > \sum_{i=1}^n x_i$ is true for all $n \ge 1$ in Hindman's sequence, simply consider the summation $$\displaystyle\sum_{i=1}^{n} x_i \le \sum_{j=s_1}^{s_1+t_1} 2^j + \sum_{j=s_2}^{s_2+t_2} 2^j + \cdots + \sum_{j=s_n}^{s_n+t_n} 2^j$$
From the definition of Hindman's sequence, we know $s_2 > s_1+t_1$, and $s_3 > s_2+t_2$, etc. This means the summations on the right-hand side never overlap indices, so that we can safely claim $$\displaystyle\sum_{i=1}^{n} x_i \le \sum_{j=0}^{s_n+t_n} 2^j = 2^{s_n+t_n+1}-1 < x_{n+1}$$
The final inequality comes from the fact that $x_{n+1}$ is divisible by $2^{s_{n+1}} \ge 2^{s_n+t_n+1}$.
This was an interesting problem...thanks for posting!