A surprising sum

The binomial expansion tells us that:

$(1+x)^n={n\choose0}x^0+{n\choose1}x^1+{n\choose2}x^2+{n\choose3}x^3+\dots+{n\choose n}x^n$

If we let $x=-1$ , we find that $x^k$ equals 1 for even $k$ and -1 for odd $k$ . Therefore:

$\begin{aligned}(1-1)^n&={n\choose0}-{n\choose1}+{n\choose2}-{n\choose3}+\dots+{n\choose n}(-1)^n\\ \therefore 0&={n\choose0}-{n\choose1}+{n\choose2}-{n\choose3}+\dots+{n\choose n}(-1)^n\end{aligned}$

$\begin{aligned}\therefore&{n\choose1}+{n\choose3}+{n\choose5}+\dots+{n\choose n-1}&=&{n\choose0}+{n\choose2}+{n\choose4}+\dots+{n\choose n}\text{ for even }n\text{, or }\\ &{n\choose1}+{n\choose3}+{n\choose5}+\dots+{n\choose n}&=&{n\choose0}+{n\choose2}+{n\choose4}+\dots+{n\choose n-1}\text{ for odd }n\end{aligned}$

In either of the above cases, the sum of all odd terms equals the sum of all even terms, and so the answer is $\boxed{\text{Yes}}$ , $A=B$ always.

A nice property of binomial coefficients is that $\displaystyle \binom{n}{k-1}+\binom{n}{k}=\binom{n+1}{k}$ , which allows us to build Pascal's triangle:

$\begin{array}{c c c c c c c c c c c c c} & & & & & & 1 & & & & & & \\ & & & & & 1 && \textcolor{#D61F06}{1} & & & & & \\ & & & & 1 && \textcolor{#D61F06}{2} && 1 & & & & \\ & & & 1 & & \textcolor{#D61F06}{3} & & 3 && \textcolor{#D61F06}{1} & & & \\ & & 1 & & \textcolor{#D61F06}{4} & & 6 & & \textcolor{#D61F06}{4} & & 1 & & \\ & 1 && \textcolor{#D61F06}{5} && 10 && \textcolor{#D61F06}{10} && 5 && \textcolor{#D61F06}{1} &\\ \vdots && \textcolor{#D61F06}{\vdots} && \vdots && \textcolor{#D61F06}{\vdots} && \vdots && \textcolor{#D61F06}{\vdots} && \vdots \end{array}$

In each row, the sum of the black numbers is $A$ and the sum of the red numbers is $B$ . Either by symmetry or by the property of construction, we conclude that $\boxed{A=B}$ .

Note that for $b<n, \binom{n}{b} = \binom{n}{n-b}$

Then the elements of A from left to right match up 1:1 with the elements of B from right to left. Therefore A=B.

Note that $\binom{n}{k} = \text{Number of non-negative integers } x < 2^n \text{, which, when written in binary, has } k \text{ digits equal to } 1.$ (in fact, this is one of the many ways to combinatorially define the binomial coefficient)

Using this as our definition, we see that $\begin{aligned} A &= \text{Number of non-negative integers } x < 2^n \text{, which, when written in binary, has an }{\color{#D61F06}\text{even}}\text{ number of digits equal to } 1 \\ B &= \text{Number of non-negative integers } x < 2^n \text{, which, when written in binary, has an }{\color{#D61F06}\text{odd}}\text{ number of digits equal to } 1 \end{aligned}$

Now, using the bitwise exclusive or $\oplus$ , we can see that

• $\displaystyle x \text{ has an even number of binary digits equal to } 1 \iff x\oplus 1 \text{ has an odd number of digits equal to } 1$
• $\displaystyle (x\oplus 1)\oplus 1 = x$

which taken together show combinatorially that $\displaystyle \boxed{A=B,}$ no matter what the value of $n$ is.

Observe Pascal's triangle.
In any row n the numbers in odd places are those which sum to A. And those in even places are the numbers which sum to B. But from the way each Pascal number is the sum of the two above... Both A and B are the sum of ALL the numbers in the row above. And are therefore equal.

In Pascal's Triangle, the sum of all the numbers in the even positions in a row give the sum of the row above, same with the odd positions.

$A=B=2^{n-1}$

Consider n tosses of a fair coin. Then A represents the number of permutations with an even number of heads and B represents the number of permutations with an odd number of heads

P (odd) = P (even) => A = B

By binomial theorem , we have $(1+x)^n = \displaystyle \sum_{k=0}^n \binom nk$ and the following.

For even $n$ :

$\begin{aligned} (1+1)^n & = \binom n0 + \binom n1 + \binom n2 + \cdots + \binom n{n-2} + \binom n{n-1} + \binom nn \\ (1-1)^n & = \binom n0 - \binom n1 + \binom n2 - \cdots + \binom n{n-2} - \binom n{n-1} + \binom nn \\ \implies A & = \frac {(1+1)^n + (1-1)^n}2 = 2^{n-1} \\ \implies B & = \frac {(1+1)^n - (1-1)^n}2 = 2^{n-1} \\ \implies A & = B \end{aligned}$

For odd $n$ :

$\begin{aligned} (1+1)^n & = \binom n0 + \binom n1 + \binom n2 + \cdots + \binom n{n-2} + \binom n{n-1} + \binom nn \\ (1-1)^n & = \binom n0 - \binom n1 + \binom n2 - \cdots - \binom n{n-2} + \binom n{n-1} - \binom nn \\ \implies A & = \frac {(1+1)^n + (1-1)^n}2 = 2^{n-1} \\ \implies B & = \frac {(1+1)^n - (1-1)^n}2 = 2^{n-1} \\ \implies A & = B \end{aligned}$

Yes , $A=B$ for all $n \ge 1$ .