My son's Sum of Some is beautiful! But what is the proof or explanation?

My youngest son is in $6$th grade. He likes to play with numbers. Today, he showed me his latest finding. I call it his "Sum of Some" because he adds up some selected numbers from a series of numbers, and the sum equals a later number in that same series. I have translated his finding into the following equation: $$(100\times2^n)+(10\times2^{n+1})+2^{n+3}=2^{n+7}.$$

Why is this so? What is the proof or explanation? Is it true for any $n$?

His own presentation of his finding:

Every one of these numbers is two times the number before it. $1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192$.
I pick any one of them, times $100$. Then I add the next one, times $10$. Then I skip the next one. Then I add the one after that.
If I then skip three ones and read the fourth, that one equals my sum!

Solution 1:

Factor out the $2^n$ and you get: $2^n (100+20+8) = 2^n 128 = 2^{n+7}$ since $2^7 = 128$

Solution 2:

It works because the number

$$ 128 $$ has two special properties: it is a power of $2$, and every digit is a power of $2$. This means that we can write it in two separate ways:

\begin{align} 128&=2^7\\ 128&=100\times2^0+10\times2^1+1\times2^3 \end{align}

Multiplying both sides by $2^n$ then gives:

$$ 2^{n+7}=(100\times2^n)+(10\times2^{n+1})+2^{n+3} $$

Edit: others have done a better job of generalizing this, but I feel I should point out another obvious related sequence.

$128$ is not the only power of $2$ whose digits are all powers of $2$ (or $0$). For instance:

$$ 1024 = 2^{10} $$

So another, similar kind of relation is given by:

$$ 2^{n+10} = (1000\times2^n)+(10\times2^{n+1})+2^{n+2} $$

In your son's notation, that becomes:

Every one of these numbers is two times the number before it.
$1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192$.
I pick any one of them, times $1000$. Then I add the next one, times $10$. Then I add the next one.
If I then skip seven (!) ones and read the eighth, that one equals my sum!

See if he likes that one.

Solution 3:

Here is another formula similar to your son's, using powers of $5$:

$$1000000\cdot5^n+100000\cdot5^{n+1}+10000\cdot5^{n+2}+1000\cdot5^{n+3}+100\cdot5^{n+4}+5^{n+6}=5^{n+9}$$

We can derive identities of a similar form more generally. Consider any $m$th degree polynomial $f(x)\in\mathbb{Z}[x]$ of the following form

$$f(x)=a_0+a_1x+\ldots+a_{m-1}x^{m-1}-x^m$$

Notice that all rational roots of $f(x)$ are integers. Suppose $f$ has a rational root $k$. Then we have the following equality:

$$\begin{align}k^{n+m}&=k^nk^m\\&=k^n(a_0+a_1k+a_2k^2+\ldots+a_{m-1}k^{m-1})\\&=a_0k^n+a_1k^{n+1}+a_2k^{n+2}+\ldots+a_{m-1}k^{n+m-1}\end{align}$$

Your son's formula involves the $7$th degree polynomial $f(x)=100+10x+x^3-x^7$ and the root $k=2$. Above I've used the polynomial $f(x)=10^6+10^5x+10^4x^2+10^3x^3+10^2x^4+x^6-x^9$ and the root $k=5$.

Here are other examples for $k=3$. Consider the polynomials $f(x)=3+8x+80x^3-x^7,$ $g(x)=2130+10x+x^3-x^7$, and $h(x)=99+687x+x^3-x^7$, and notice that $f(3)=g(3)=h(3)=0$. These give us the following identities:

$$3\cdot3^n+8\cdot 3^{n+1}+80\cdot3^{n+3}=3^{n+7}\\2130\cdot3^n+10\cdot3^{n+1}+3^{n+3}=3^{n+7}\\99\cdot3^n+687\cdot3^{n+1}+3^{n+3}=3^{n+7}$$

Try using this method to find identities for other values of $k$ (including negative integers!).

Solution 4:

A proof which, unlike all other suggestions, doesn't require power as a prerequisite.

This is what your son noticed by himself by looking at the first occurences in the sequence:

1 × 100 + 2 × 10 + 8 = 128

Now, let him remark that he can multiply everything by 2 without affecting the equality:

2 × (1 × 100 + 2 × 10 + 8) = 2 × 128

Assuming that he understands that the doubling distributes over the sum, he will obtain:

2 × 1 × 100 + 2 × 2 × 10 + 2 × 8 = 2 × 128

Then remark that when you double any pick you obtain of course the next pick in the sequence:

2 × 100 + 4 × 10 + 16 = 256

Repeat. Multiply both sides by two, distribute and double every pick again, and you obtain one more equality:

4 × 100 + 8 × 10 + 32 = 512

Repeat.

Now he should be pretty much convinced that his statement holds for any pick. (Of course it could be a good opportunity to introduce recurrence!)

Solution 5:

You may observe that whenever in any geometric progression $a_n=\lambda^na_0$, one term satisfies a linear recurrence ($a_n=c_0a_0+c_1a_1+\cdots+c_{n-1}a_{n-1}$, where some coefficients $c_i$ may be zero and the corresponding terms dropped), then every further term of the sequence satisfies the same recurrence: $a_{i+n}=c_0a_i+c_1a_{i+1}+\cdots+c_{n-1}a_{i+n-1}$. This is because the relation has simply been multiplied by $\lambda^i$. Even every term in another geometric progression with ratio$~\lambda$ will satisfy the recurrence.

What make the example especially attractive is that the nonzero coefficients are all powers of$~10$, which makes the linear combination easy to compute; this is related to the fact that all (nonzero) digits of $2^7=128$ themselves occur as powers of $2$. The same phenomenon happens for $2^{10}=1024$: take $1000$ times some power of$~2$, add $10~$times the next power of two, and once the one after that; the result is present again $8~$places further in the same progression. (For the digits of $2^{11}=2048$ you basically get the same relation.)