Andrei Lazanu from School 205, Bucharest, Romania and Yatir Halevi 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:

n ones 11... 11   × nones 11... 11   = (n−1) ones 11... 11   n zeros 00... 00   1 one 1   .

This means that squaring a number containing only '1s', 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 ₁₀ = 5*10 ³ + 4*10 ² + 3*10 ¹ + 2*10 ⁰), every binary number can be expressed as a sum of powers of 2: (1010 ₂ = 1*2 ³ + 0*2 ² + 1*2 ¹ + 0*2 ⁰.

So 1111 ₂ is the sum of four powers of 2:

1111 ₂ = 2 ³ + 2 ² + 2 ¹ + 2 ⁰ = 2 ⁴ - 1.

The binary number written with n ones is the sum of n powers of 2 (a geometric series) equal to 2 ⁿ - 1.

(2n − 1)2 = 22n − 2n+1 + 1

= (22n − 1)−(2n+1 −1)+ 1

= (a string of 2n ones )−(a string of (n+1) ones ) + 1

=(a string of (n−1) ones and after them a string of n zeros and then 1 )

Ill illustrate what I said above with an example showing that 1111 ² = 11100001 More formally, if we have N = 11111...111 with n ones, then

N = 1+2 + ... 2n−1 = 2n − 1.

Thus

N2 = 22n−2n+1+1 = 2n+1(2n−1−1) + 1 = 2n+1(1+2+ ... +2n−2) + 1 = 22n−1+ 22n−2 + ... 2n+1 + 1.

So N ² 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:

k+1 ones 11... 11   = 1 k zeros 0... 0   + k ones 11...11

It follows that the square of the binary number with k+1 digits (all ones) is given by:

k+1 ones (11...11)2   = (1 k zeros 0...0   + k ones 11...11   )2

= 1 2k zeros 00...00   + 10 ×1 k zeros 00...00   × k ones 11...11   + k−1 ones 11...11   k zeros 00...00   1 one 1

= 1 2k zeros 00...00   + k ones 11...11   k+1 zeros 00...00    + k−1 ones 11...11   k zeros 00...00   1 one 1

Thus:

k+1 ones (11...11)2   = k ones 11...11   k+1 zeros 00...00   1 one 1

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