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 (t
1) is
twice the first term.
The second two terms (t
2 and t
3) are twice the first two terms,
respectively.
The second group of
four terms are twice the
first group of four terms.
...
In
general, 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
t
n=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 in
binary:
n=0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, ...
t
n=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.