When you sum the even terms and the odd terms of the binomial coefficient you get the same number, how can i prove this?

45 Views Asked by At

I am trying to that a function which outputs either 0 or 1 is balanced (has the same number of outputs which are 0 and which are 1). I've essentially proved that this is the case if the sum $\sum^{l}_{j=1}x_{j}$, where each $x_{j}$ is a bit so can take values of either 0 or 1, has the same number of even outcomes as odd outcomes. For the sum to evaluate to some value, x we have $\dbinom{l}{x}$ combinations (e.g 1 combination where the sum adds to 0, l where it adds to one e.t.c). So, if $l$ is an even number, there are $$\sum^{l}_{i=0}\dbinom{l}{2i}$$ combinations of different $x_{j}$ which will given even outputs and $$\sum^{l}_{i=1}\dbinom{l}{2i-1}$$ which give odd outputs. Looking at pascals triangle, it's clear that these are equal. However I can't quite prove it. My method has been to subtract the two from eachother, such that I end up with $$\sum^{l}_{i=1}[\dbinom{l}{2i}-\dbinom{l}{2i-1}]+1$$ Since $\dbinom{l}{0}=1$. However I can't seem to get a sum that will clearly evaluate to 1 when I try to expand out the binomial coefficient terms.