Is it true that $\sum_{i=0}^{n-1} 2^i$ divides $\sum_{i=n}^{2n-1} 2^i$?

Question

Some investigation suggested to me that

$$\sum_{i=0}^{n-1} 2^i \Bigg| \sum_{i=n}^{2n-1} 2^i$$

The point being that binary numbers in the form exclusively of an even number of $1$s appear to be divisible by the number represented by just half that number of $1$s.

Is this the case, and if so why is that please?

Answer 1

Note you have

$$\begin{equation}\begin{aligned} \sum_{i=n}^{2n-1} 2^i & = 2^n + 2^{n+1} + \ldots + 2^{2n-1} \\ & = 2^n + 2^n(2) + \ldots + 2^n(2^{n-1}) \\ & = 2^n(1 + 2 + \ldots + 2^{n-1}) \\ & = \sum_{i=0}^{n-1} 2^n(2^i) \\ & = 2^n\left(\sum_{i=0}^{n-1} 2^i\right) \end{aligned}\end{equation}\tag{1}\label{eq1A}$$

Answer 2

Well, you don't even need to know something about summation.

As you noticed, the binary representation of the first number (i.e., $\sum_{i=0}^{n-1}2^i$), say $s$, is made only by $1$s, so if you add the number 1 you'll get a $1$ followed only by $0$s, namely a power of $2$: which one? The number $s$ has $n$ digits, and then, due to the carries, $s+1$ has $n$ digits and so it is $2^n$, i.e., the first power of two greater than $2^{n-1}$.

The same argument show that the value of the second sum is $2^{2n}-2^n$, indeed it is the sum of all the powers of two from $2^0$ to $2^{2n-1}$, which is $2^{2n}$, minus all the powers of two from $2^0$ to $2^{n-1}$, which is $2^n$. Now $2^{2n}-2^n=2^{n}(2^n-1)$, which is what you wanted to prove.

---

If this is clear, now you're able the extend this result also to the powers of any number. Indeed, for a natural number $a>1$, consider the following equalities (first you have to use distributivity, then the "trick" is to detach the first or the last addend of the sums from the others, i.e., to use the associative property): \begin{split}(a-1)\sum_{i=0}^{n-1}a^i=& a\sum_{i=0}^{n-1}a^i-\sum_{i=0}^{n-1}a^i=\sum_{i=1}^{n}a^i-\sum_{i=0}^{n-1}a^i=\\&=\left(\sum_1^{n-1}a^i+a^n\right)-\left(a^0+\sum_{i=1}^{n-1}a^i\right)=a^n-1.\end{split} Now, dividing by $a-1$, you have a closed form for the summation $\sum_{i=0}^{n-1}a^i$, namely $$\sum_{i=0}^{n-1}a^i=\frac{a^n-1}{a-1}$$ (notice that we're not using the fact that $a$ is a natural number, we only need $a\neq 0$, so the formula holds for $a\in\mathbb{R}\setminus\{0\}$).
Knowing this, you have $$\sum_{i=n}^{2n-1}a^i=\sum_{i=0}^{2n-1}a^i-\sum_{i=0}^{n-1}a^i=\frac{a^{2n}-1}{a-1}-\frac{a^n-1}{a-1}=\frac{a^{2n}-a^n}{a-1}=a^n\frac{a^n-1}{a-1}=a^n\sum_{i=0}^{n-1}a^i.$$ In this way, not only you can prove that $\sum_{i=n}^{2n-1}a^i$ is divisible by $\sum_{i=0}^{n-1}a^i$, but also that the quotient is exactly $a^n$.

---

Lastly, we can came back to your original intuition. Given a natural number $a>1$, the $a$-ary representation of a power of $a$, say $a^j$, is made by a $1$ followed by $j$ $0$s, so the $a$-ary representation of the sum $a^0+a^1+\ldots +a^{n-1}$ is simply made by $n$ consecutive $1$s. For the same reason, the representation of $a^n+a^{n+1}+\ldots +a^{2n-1}$ is made by $n$ consecutive $1$s followed by $n$ consecutive $0$s. Now, you can perform the long division between those two numbers: you'll have something like this

$$ \require{enclose} \begin{array}{r} 1\overbrace{00\ldots 0}^{n\text{ digits}} \\[-3pt] \underbrace{11\ldots 1}_{n\text{ digits}} \enclose{longdiv}{\underbrace{11\ldots 1}_{n\text{ digits}}\underbrace{00\ldots 0}_{n\text{ digits}}} \\[-3pt] \underline{11\ldots 1}\phantom{00\ldots 0} \\[-3pt] 00\phantom{0\ldots 0} \\[-3pt] \underline{0}\phantom{0\ldots 0} \\[-3pt] 00\phantom{\ldots 0} \\[-3pt] \ldots \end{array} $$

so the division is exact and the quotient is the number with $n+1$ digits $10\ldots 0$ in base $a$, that is $a^n$, as expected.

The same argument proves the observation made by probably_someone, i.e., that a number consisting of $n$ consecutive $1$s followed by any number of consecutive $0$s is divisible by a number consisting of $n$ consecutive $1$s. Actually, we can say something more: for any $k\in\mathbb{N}$, consider $a_1,a_2,\ldots ,a_k\in\mathbb{N}$, then a number consisting of $na_1$ consecutive $1$s followed by any number of consecutive $0$s followed by $na_2$ consecutive $1$s followed by any number of consecutive $0$s ... followed by $na_k$ consecutive $1$s followed by any number of consecutive $0$s is divisible by a number consisting of $n$ consecutive $1$s.

Answer 3

An alternative answer, by construction:

In binary, multiplying a number by 2 is equivalent to shifting all of its bits one place higher and adding a zero on the end. Consequently, multiplying by $2^n$ just means doing that $n$ times, moving the bits $n$ places higher and adding $n$ zeros.

The object is to prove that a number consisting of $n$ consecutive ones and $n$ consecutive zeros is divisible by the number consisting of $n$ consecutive ones.

Knowing what we know about multiplication by $2$ in binary, it should be straightforward how to get from the smaller number to the larger one: just shift its digits $n$ places higher and add $n$ zeros; in other words, multiply by $2^n$. Since we can multiply the smaller number by an integer to get to the larger number, this means that the larger number is divisible by the smaller one.

In fact, this method can be used to prove a stronger statement: a number consisting of $n$ consecutive ones followed by any number of consecutive zeros is divisible by a number consisting of $n$ consecutive ones.