Adventures with Pascals triangle and Binary

Numbers
Daniel Mathews
November 10, 2004
Some of us have probably seen the following array of numbers before:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
.
.
.
Where, as one can see, each entry is obtained by adding the two entries
directly above it Pascals triangle as its known.
All sorts of fun stu occurs when one plays around with Pascals triangle.
For instance, lets look at the parity of the numbers in this triangle (ie, whether
theyre even or odd) as one does, of course! Lets count how many odd and
even numbers there are in each row.
Number of Number of
Odd Entries Even Entries
1 1 0
1 1 2 0
1 2 1 2 1
1 3 3 1 4 0
1 4 6 4 1 2 3
1 5 10 10 5 1 4 2
1 6 15 20 15 6 1 4 3
.
.
.
.
.
.
.
.
.
Im particularly interested in the number of odd entries in each row, because
they turn out to be quite odd. (Sorry about that one, I just couldnt help it).
We obtain the following sequence of numbers:
1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, . . .
If you look at that one for a while, it turns out to be quite interesting. But
well delay that for a bit. Lets turn our mind to something equally obscure...
1
remember binary numbers from school? Yes thats right, those numbers which
only used the digits 0 and 1 (not 2 through 9), and where the place value of
each digit was not 1, 10, 100, 1000 and so on, but instead 1, 2, 4, 8, etc.
Lets write out the rst few numbers in binary, starting from zero, just to
get the hang of it:
0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, . . .
Hmmmm, well writing out binary numbers is one way to spend a rainy day.
But now lets consider the number of 1s in the binary representation of each
number.
Number in decimal 0 1 2 3 4 5 6 7 8 9 10
Number in binary 0 1 10 11 100 101 110 111 1000 1001 1010
Number of 1s 0 1 1 2 1 2 2 3 1 2 2
Well what the heck, after all that experience I bet were feeling a bet wild
so lets do something crazy lets take all these numbers we just got (that is,
the number of 1s in each numbers binary representation), and lets take 2 to
the power of it. We get:
1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, . . .
which looks entirely familiar... yes, it looks like these two sequences, the
number of odd entries in each row of Pascals triangles, and the number of
1s in the binary representation of each number, are in cahoots! Yes theyre
identical! This leads us to the remarkable equation, generalising what we just
saw:
{#Odd entries in nth row of Pascals triangle} = 2
{#1s in binary representation of n}
This is indeed an obscure connection. But we can prove it. Well, Im not
going to prove it rigorously but Ill give you the idea. Firstly, look at how the
odds and evens appear in Pascals triangle:
2
Odd
Even
This looks quite remarkable and, for those who know something about frac-
tals, it has exactly the same pattern as the Sierpinski gasket. The rows with all
odd numbers are rows number 0, 1, 3, 7, 15, . . .. These look like all the numbers
which are one less than a power of 2, and in fact this is true all rows numbered
2
n
1 for some n have all entries odd. You see, when we have an all-odd row,
the next row is all-even, so the odds wipe themselves out completely (since each
entry in the next row is the sum of the two entries above it odd + odd =
even). But not quite completely the two extremities of the next row are odd,
as each of them only has one entry above it. So now we have two odd entries
in the next row (row number 2
n
), at the very extremities.
But what happens now? The whole process starts again, TWICE! That
is, the two odd entries at either side start entirely new versions of the original
triangle, in exactly the same pattern! And they dont intersect for a while
because they are so far apart they can only spread down like the original
triangle. In fact, they are just so far apart (you can check it if you like) so that,
at the next power-of-two-minus-one, 2
n+1
1, they are just about to intersect
and the row is all odd again! So the odds wipe themselves out again and the
doubling process starts all over again, so on and so forth.
What has this got to do with binary numbers? Well the power of 2 gives
us a clue. We can actually write an equation out of my last two paragraphs of
rambling, believe it or not. First, let the number of odd entries in the nth row
be f(n). We already know because of our wipe-out theory that at every power
of 2 there are only 2 odd entries, so f(2
k
) = 2 for all possible k. Because of
the way that the triangle replicates itself twice, if we go, say x steps beyond the
doubling point 2
n
, then the point we get to is a point x steps into the original
triangle, copied twice. So the number of odd entries in row number 2
n
+ x is
twice the number of odd entries in row number x. That is,
f(2
n
+ x) = 2f(x).
3
Excellent! But we have to remember that this doesnt work for all x, because
if we go too far past 2
n
the triangle will have wiped itself out again. We can
check that it only works for x between 0 and 2
n
1. Phew!
Now to bring the binary numbers into it. When a number is written in
binary form, we are basically writing it as a sum of powers of 2. For example,
10
2
= 2
1
1101
2
= 2
3
+ 2
2
+ 2
0
So, if we think about it, we can use the f formula on these powers of 2
because, for instance,
f(2
3
+ 2
2
+ 2
0
) = f(2
3
+ other stu)
= 2f(other stu)
(You can check for yourself that the other stu is always within the right
limits). We can now use this idea to gure out f of some numbers.
f(10
2
) = f(2
1
) = 2 (as f of a power of 2 gives 2)
f(1101
2
) = f(2
3
+ 2
2
+ 2
0
)
= f(2
3
+ (2
2
+ 2
0
))
= 2f(2
2
+ 2
0
)
= 4f(2
0
)
= 8
And so, we can see, for every power of 2 in the sum, we have a factor of 2!
But the number of powers of 2 we write out is just the number of digits in the
binary representation. So we have a connection! To see this more clearly, take
any old binary number with, say, m 1s in it.
m 1s m terms

1101011101 101

2
stu
+ 2
other stu
+ + 2
more stu
f(2
stu
+ 2
other stu
+ + 2
more stu
)
2f(2
other stu
+ + 2
more stu
)
(m times)
2
m
4
And so we have it, O intrepid mathematical adventurers! This proves the
result.
5