Moderator Note: This question is from a contest which ended 1 Dec 2012.
Consider Pascal's Triangle taken $\pmod 2$:
For simplicity, we will call a finite string of 0's and 1's proper if it occurs in one of the rows of this modified Pascal's triangle. (for example, 0 (row 3) and 10001 (row 5) are proper).
I've been exploring proper strings of length $n$. My professor told me it is possible to
i) characterize explicitly all proper strings of length $n$
and ii) Find an explicit formula for the number of proper strings of length $n$.
But I cannot figure out how to even begin either parts. This is a very interesting problem, and I was wondering if someone could help me. Thank you!