Problem

Source: 2002 Singapore TST 1.2

Tags: Sequence, combinatorics, odd, Even



Let n be a positive integer and (x1,x2,...,x2n), xi=0 or 1,i=1,2,...,2n be a sequence of 2n integers. Let Sn be the sum Sn=x1x2+x3x4+...+x2n1x2n. If On is the number of sequences such that Sn is odd and En is the number of sequences such that Sn is even, prove that OnEn=2n12n+1