Every natural number in binary can be cut and added so that it is a power of $2$?

141 Views Asked by At

I was watching a google techtalk with Donald Knuth and he mentions for every binary number $\overline{a_1a_2a_3\dots a_n}$ there exists $c_1<c_2<\dots <c_r=n$ so that:

$\overline{a_1a_2\dots a_{c_1}}+\overline{a_{c_1+1}a_{c_1+2}\dots a_{c_2}}+ \dots + \overline{a_{c_{r-1}+1}a_{c_{r-1}+2}\dots a_{c_r}}$ is a power of $2$.

Or in other words: every binary number can be separated into continuous pieces, which add up to a power of $2$. I have tried proving this for a bit, but I haven't gotten anywhere.