Binary Squares

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$:

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$.

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$:

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