Copyright © University of Cambridge. All rights reserved.

'Binary Squares' printed from http://nrich.maths.org/

Show menu


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