Binary Expansion of 2^n-1

Question

Show that the positive integral multiples of $2^{n}-1$ when expressed in binary will have at least $n$ ones'.

My work so far:

Let $b(k)$ be the number of ones when k is expressed in binary and let $e(n)$ be the number of factors of 2 dividing $n$. I found that $$b(n-1)=b(n)+e(n)-1.$$

So i know that $b(2^n-1)\ge{n}$ but i have a hard time proving it for $b(k2^{n}-k)$. I thought about going by induction but i was unable to proceed. Any ideas on this problem?

Answer 1

Let $k$ be the smallest number that $k(2^n-1)$ has at most $n-1$ ones in binary expansion.

(1) $k$ is even. The number ${k\over2}<k$ generates at most $n-1$ ones in ${k\over2}(2^n-1)$ as well, contradiction.

(2) $k$ is odd and $k\geq3$. Consider the number $k+1\over2$.

We can see that $(k+1)(2^n-1)=k(2^n-1)-1+2^n$ has at most the same number of ones as $k(2^n-1)$ has because $k$ is odd.

First, we look at the number $k(2^n-1)-1$, since $k$ is odd, this number has exactly $1$ less one than the number $k(2^n-1)$.

Then we compare the number $k(2^n-1)-1+2^n$ with $k(2^n-1)-1$. If the $(n+1)$th digit of $k(2^n-1)-1$ is $0$, then $k(2^n-1)-1+2^n$ has exactly $1$ more one than $k(2^n-1)-1$ and thus the same number of ones as $k(2^n-1)$. If the $(n+1)$th digit of $k(2^n-1)-1$ is $1$, say the $m$ digits starting from the $(n+1)$th digit are all ones ($m \geq 1$) and that the $(n+m+1)$th digit is $0$, then after adding $2^n$, the $(n+m+1)$th digit becomes $1$ and the $m$ digits become $0$. Since $m\geq1$, we have less or equal ones after adding the $2^n$.

Hence $(k+1)(2^n-1)$ has at most the same number of ones as $k(2^n-1)$. However, since $k$ is odd, $k+1$ is even and ${k+1\over2}$ is a smaller number than $k$ such that ${k+1\over2}(2^n-1)$ has at most $n-1$ ones.

Since $k\geq3$, ${k+1\over2}$ is a positive integer less than $k$, contradiction.

(3) $k=1$. Since $k(2^n-1)$ has $n$ ones, contradiction.