Copyright © University of Cambridge. All rights reserved.
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