$\binom {100} 0 \binom{100}{98}+\binom{100}2 \binom{100}{96}+\cdots+\binom{100}{98} \binom{100}0$

517 Views Asked by At

$$\binom {100} 0 \binom{100}{98}+\binom{100}2 \binom{100}{96}+\cdots+\binom{100}{98} \binom{100}0$$

Clearly the sum of bases is 98. I have solved this problem algebraically by finding half of Coefficient of $x^{98}$ in $$(1+x)^{100}(1+x)^{100}+(1-x)^{100}(1+x)^{100}$$ The answer comes out to be $$\frac{\binom{200}{98}-\binom{100}{49}}{2}$$

I wanted a combinatorial intuition behind it I framed a situation as if there are 2 bags and in total we need to pick 98 balls each contains 100 balls and we can only choose even number of balls from each bag and I'm stuck after this

1

There are 1 best solutions below

1
On BEST ANSWER

Let us imagine that we have two parallel rows of lamps. Red lamps with numbers from $1$ to $100$. And blue lamps with numbers from $1$ to $100$. As you stated the big sum in the title (denote it by $S$) is the number of combinations where $98$ lamps are switched on so that even number of lamps in every row is on. Let us prove that the number of combinations where $98$ lamps are switched on so that ODD number of lamps in every row is on is greater by $100 \choose 49$. Then it is obviously equivalent to $S=( {200 \choose 98}-{100 \choose 49})/2$ since ${200 \choose 98}$ is the number of all combinations of $98$ lamps switched on.

Let us try build a bijection between all the “even” and “odd” cases. Take some combination of $98$ lamps switched on. Let $i$ be the maximum number from $1$ to $100$ such that exactly one lamp with number $i$ is switched on. Inverse the two lamps. The “even” case became the “odd” one and vice versa. So the “even” and “odd” cases go in pairs, almost. The only group of cases when there is no pair is when all the lamps with same numbers are in the same state. There is clearly $100 \choose 49$ such combinations, and they are all “odd”. We are done.