6
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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}$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm quite new to summation notation. Could you possibly elaborate on the steps from each form to the next here please? $\endgroup$ – Robin Andrews Jul 26 at 9:29
  • 1
    $\begingroup$ @RobinAndrews This is the distributive law. $\endgroup$ – Angina Seng Jul 26 at 9:37
  • 2
    $\begingroup$ @RobinAndrews I expanded the summation and showed that each term has a factor of $2^n$. Removing that common factor, you have then the sum of the powers of $2$ from $0$ to $n - 1$. I hope this makes it more clear to you. $\endgroup$ – John Omielan Jul 26 at 9:39
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm having trouble following your argument. "As you noticed...namely a power of 2, so the first sum is the first power of two greater than 2n−1, i.e. 2n." I get that "all 1s" is 1 less than the next power of 2, but how does this imply that the sum is the next power of 2? What am I missing here please? $\endgroup$ – Robin Andrews Jul 26 at 17:05
  • $\begingroup$ @RobinAndrews I've made an edit, in short: just count the digits of that number. $\endgroup$ – user6530 Jul 26 at 19:37
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.