Binary squares
Problem
If a number N is expressed in binary by using only 'ones,' what can you say about its square (in binary)?
Getting Started
Is there a general pattern of $1$'s and $0$'s in a binary number which is the square of a binary number containing only $1$'s? Try squares of $11$, $111$, $1111$ etc? To generalize you might use the fact that the sum of powers of two is a geometric series.
Student Solutions
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$.
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