Some unique representation of nonnegative integers

225 Views Asked by At

Let $\mathbb N$ be the set of nonnegative integers, that is $\mathbb N=\{0,1,2,3,\ldots\}$.

Does there exist a subset $K\subset\mathbb N$ such that every $n\in\mathbb N$ has a unique representation $n=a+2b$ with $a,b\in K$?

I have got the partial results that $0\in K$, $1\in K$, $2\notin K$, $3\notin K$, $4\in K$, $5\in K$, $6\notin K$, $7\notin K$, $8\notin K$, $9\notin K$, $10\notin K$, $11\notin K$, $12\notin K$, $13\notin K$, $14\notin K$, $15\notin K$, $16\in K$, $17\in K$.

1

There are 1 best solutions below

5
On

In terms of generating functions let $f(x)=\sum_{a\in K}x^a$. You have: $$\frac{1}{1-x}=\sum_{i=0}^{\infty}x^i=\sum_{a,b\in K}x^{a+2b}=\left(\sum_{a\in K}x^a\right)\left(\sum_{a\in K}x^{2a}\right)=f(x)f(x^2)\tag{1}.$$

Now in order to construct $K$ it suffices to find the function $f$. One way to do this is to prove that there is a unique subset $K$ which verifies the equation $(1)$ by induction and differentiation and evaluating at $x=0$, but you can find the generating function $f$ by the following formula: $$\left(1-x^{2^{2n+1}}\right)f(x)f\left(x^{2^{2n+1}}\right)=\prod_{i=0}^{n}\frac{1-x^{2^{2i+1}}}{1-x^{2^{2i}}}\tag{2}$$

and when $n\to \infty$ we can conclude that: $$f(x)=\prod_{i=0}^{\infty}\frac{1-x^{2^{2i+1}}}{1-x^{2^{2i}}}=\prod_{i=1}^{\infty}\left(1+x^{2^{2i}}\right) \tag 3$$

and finally we proved that $K$ is unique and $$K=\left\{\sum_{i\in A} 2^{2i}\ \big|\ A\subset \Bbb N,|A|<\infty\right\} \tag 4$$

and hence we proved that $K$ must be the set of integers whose binary representation have always zero in odd positions.

Maybe one can find this result in the beginning because every integer $n$ has a unique representation of the form $$n=\sum_{i\in A}2^i+2\sum_{i\in B}2^i\tag 5$$ with $A,B$ contain only even numbers.