You may also like

problem icon

Code to Zero

Find all 3 digit numbers such that by adding the first digit, the square of the second and the cube of the third you get the original number, for example 1 + 3^2 + 5^3 = 135.

problem icon

Basic Rhythms

Explore a number pattern which has the same symmetries in different bases.

problem icon

Learn about Number Bases

We are used to writing numbers in base ten, using 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Eg. 75 means 7 tens and five units. This article explains how numbers can be written in any number base.

Binary Squares

Stage: 5 Challenge Level: Challenge Level:2 Challenge Level:2

Andrei from School 205, Bucharest, Romania and Yatir from Maccabim-Reut High School, Israel both spotted the pattern in the squares (in binary) of numbers that are expressed in binary by using only `ones'. Andrei proved the rule using induction and Yatir proved it using geometric series.

First this is Andrei's description of the rule.

I start by considering the successive multiplications in base $2$:

$1 \times 1$
$=$ $1$
$11 \times 11$
$=$ $1001$
$111 \times 111$
$=$ $11001$
$1111 \times 1111$
$=$ $11100001$
$11111 \times 11111$
$=$ $1111000001$

Now I guessed the rule:

$$\overbrace {11... 11}^{n ones} \times \overbrace {11... 11}^{n ones} = \overbrace {11... 11}^{(n-1) ones}\overbrace {00... 00}^{n zeros }\overbrace{1}^{1 one}.$$

This means that squaring a number containing only '$1$s', written in base $2$ we obtain a number containing ($n$-1) digits of '$1$', followed by $n$ digits of '$0$' and a last digit '$1$'. The product has $2n$ digits.

Andrei then proved this rule by mathematical induction but first let's see how Yatir proved it. Here is Yatir's solution.

In this proof $m_n$ will mean that the number $m$ is in base $n$.

Just like every decimal number can be expressed as a sum of powers of $10$: ( $5432_{10} = 5 \times 10^3 + 4 \times 10^2 + 3 \times 10^1 + 2 \times 10^0$ ), every binary number can be expressed as a sum of powers of $2$: ($1010_2 = 1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 0 \times 2^0$).

So $1111_2$ is the sum of four powers of $2$:

$1111_2 = 2^3 + 2^2 + 2^1 + 2^0 = 2^4 - 1$.

The binary number written with $n$ ones is the sum of $n$ powers of 2 (a geometric series) equal to $2^n - 1$.

\[(2^n - 1)^2 = 2^{2n} - 2^{n+1} + 1 \] \[= (2^{2n} - 1)-(2^{n+1} -1)+ 1 \] \[= (\rm{a\ string\ of\ 2n\ ones\ })-(\rm{a\ string\ of\ (n+1)\ ones\ }) + 1 \] \[=(\rm {a\ string\ of\ (n-1)\ ones\ and\ after\ them\ a\ string\ of\ n\ zeros\ and\ then\ 1\ }) \]

I'll illustrate what I said above with an example showing that
$1111^2 = 11100001$
\[(2^4 - 1)^2 = 2^8 - 2^5 + 1 \] \[ = (2^8 - 1)-(2^5 - 1)+ 1 \] \[ =(\rm {a\ string\ of\ 8\ ones })-(\rm{a\ string\ of\ 5\ ones\ })+ 1\] \[ =(\rm {a\ string\ of\ 3\ ones\ and\ after\ them\ a\ string\ of\ 4\ zeros\ and\ then\ 1\ })\] More formally, if we have $N = 11111...111$ with $n$ ones, then

$$N = 1+2 + ... 2^{n-1} = 2^n - 1.$$

Thus

$$\eqalign{N^2 &= 2^{2n}-2^{n+1}+1\cr &= 2^{n+1}(2^{n-1}-1) + 1\cr &= 2^{n+1}(1+2+ ... +2^{n-2}) + 1\cr &= 2^{2n-1}+ 2^{2n-2} + ... 2^{n+1} + 1.}$$

So $N^2$ in binary is (from the left) a string of $n-1$ ones and after them a string $n$ zeros and after them $1$.

Now this is Andrei's rather different proof:

Now I have to prove this formula by induction. We assume the result is true for $n = k$ and then square a number with $(k+1)$ digits, all '$1$'. In base $2$:

$$\overbrace {11... 11}^{k+1\ \rm{ones}} = 1\overbrace{0... 0}^{k\ \rm{zeros}} + \overbrace {11... 11}^{k\ \rm{ones}}$$

It follows that the square of the binary number with $k+1$ digits (all ones) is given by:

$$\overbrace {(11...11)^2}^{k+1 ones} = {(1 \overbrace{0...0}^{k zeros} + \overbrace{11...11}^{k ones})^2} $$

$$ = {1 \overbrace {00...00}^{2k zeros} + 10 \times 1 \overbrace{00...00}^{k zeros} \times \overbrace {11...11}^{k ones} + \overbrace {11...11}^{k-1 ones} \overbrace{00...00}^{k zeros} \overbrace {1}^{1 one}} $$

$$ = {1 \overbrace {00...00}^{2k zeros} + \overbrace {11...11}^{k ones} \overbrace{00...00}^{k+1 zeros}\ + \overbrace {11...11}^{k-1 ones} \overbrace{00...00}^{k zeros} \overbrace {1}^{1 one}} $$

Thus:

$$\overbrace {(11...11)^2}^{k+1 ones} = {\overbrace {11...11}^{k ones} \overbrace{00...00}^{k+1 zeros} \overbrace {1}^{1 one} } $$

To get the last line above I added the digits order by order. This proves the result is true for all integers by the method of induction