Binary Squares

Age 16 to 18

Challenge Level Yellow star

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

Number and algebra

Geometry and measure

Probability and statistics

Working mathematically

Advanced mathematics

For younger learners

Binary Squares

You may also like

Code to Zero

Basic Rhythms

Learn about Number Bases