An interesting problem is to determine the number of odd coefficients in the expansion of (x+y)n. Essentially, this reduces to determining the number of odd values in the n-th row of Pascal's Triangle.
One might begin an investigation into this problem by calculating the triangle to a reasonably large number of rows. With such a large triangle, it is possible to begin looking for patterns. However, there is a clever trick to save oneself a lot of work! Since we are only concerned with the entries' even-ness or odd-ness (i.e. their parity), we can just make Pascal's Triangle in modulus 2. That is, we create the triangle in the same way, but count the value of 1+1 as 0. As Uberfetus pointed out above, this results in a pattern like a Sierpinski Triangle.
Now we can start counting the number of ones, which correspond to the odd elements of the original triangle. What we find is a sequence:
1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, ...
What to make of a sequence like this? (Caveat: The "first" term is actually t0, because the top row of Pascal's Triangle is the "zero-th".) Some observations:
The second term (t1
) is twice
the first term.
The second two terms (t2
) are twice the first two terms, respectively
The second group of four
terms are twice the first
group of four terms.
, the second group of 2^n terms are twice the first group
of 2^n terms.
Hmm. Clearly there is a nested, fractal-like pattern of doubling present. But how does this help us define explicitly the value of the n-th term? That is, we wish to establish a relation between the lists:
n=0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,..., and
=1, 2, 2, 4, 2, 4, 4, 6, 2, 4, 4, 8, 4, 8, 8, 16
Note that the number two
is key to the pattern
we are investigating. On a hunch
, let's rewrite our indices
n=0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, ...
=1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16,...
Do you see it yet? Keep looking.... Yes! In general,
tn=2^(# of ones in the binary representation of n).
This may sound weird, but think about it in relation to the nested pattern of doubling we noticed in the sequence originally. By writing the index in binary, we are implicitly locating it within our fractal structure. Each one in its binary representation is another level of nesting. Since each level represents a doubling, we can just raise 2 to the power of the number of these levels!
To put this back into the context of our original question...
To find the number of odd coefficients in (x+y)n, we write n in binary and count the number of ones. Calling this number p, the number of odd coefficients can be calculated as 2p.