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*1
|
= |
1
|
11*11
|
= |
1001
|
111*111
|
= |
11001
|
1111*1111
|
= |
11100001
|
11111*11111
|
= |
1111000001
|
Now I guessed the rule:
|
|
n ones
11... 11
|
× |
n ones
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 10 = 5*10 3 + 4*10
2 + 3*10 1 + 2*10 0 ), every
binary number can be expressed as a sum of powers of 2: (1010
2 = 1*2 3 + 0*2 2 + 1*2
1 + 0*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.
|
(2n - 1)2 = 22n - 2n+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 ) |
|
I'll illustrate what I said above with an example showing that
1111 2 = 11100001
|
= (a string of 8 ones )-(a string of 5 ones )+ 1 |
|
|
= (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 + ... 2n-1 = 2n - 1. |
|
Thus
|
|
| |
| |
|
= 2n+1(1+2+ ... +2n-2) + 1 |
| |
| = 22n-1+ 22n-2 + ... 2n+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:
|
|
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