The sum of all the binomial coefficients (n choose j), as j goes from 0 to n, is 2^n, which is even. The coefficients pair off, with (n choose j) = (n choose n–j), and obviously the sum of each pair is even. If n=2k is even, there is a "left-over" term (2k choose k), in the middle of the sequence, which does not pair off with another term. In order for the sum of the whole sequence to be even, this term must clearly be even.