Challenge Level

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