The value of $r$ for which $\binom {20}{r} \binom{20}{0} +\binom{20}{r-1}\binom{20}{1}...\binom{20}{0} \binom{20}{r}$ is maximum is?

Question

Most solutions write the given expression as $$(1+x)^{20}(1+x)^{20}=(1+x)^{40}$$

But I can’t wrap my head around has to how it is even correct to do so.

When you expand the factors, what about all the other residual terms such $(\binom {20}{0})^2$ that aren’t included in the question expression?

I know this question already exists on MSE, no it does not clear the specific problem I have

Answer 1

It’s just a matter of equating the coefficients of $x^r$ in two different ways of writing the same polynomial. For each $r$ from $0$ through $40$ the coefficient of $x^r$ on the lefthand side of the equation

$$(1+x)^{20}(1+x)^{20}=(1+x)^{40}\tag{1}$$

is

$$\begin{align*} &\binom{20}r\binom{20}0+\binom{20}{r-1}\binom{20}1+\ldots+\binom{20}0\binom{20}r\\ &\qquad=\sum_{k=0}^r\binom{20}{r-k}\binom{20}k\,, \end{align*}\tag{2}$$

which is the expression that you want to maximize. The coefficient of $x^r$ on the righthand side of $(1)$ is $\binom{40}r$. These coefficients must be equal, so

$$\sum_{k=0}^r\binom{20}{r-k}\binom{20}k=\binom{40}r\,,\tag{3}$$

which we know is maximized when $r=20$.

In more detail, the lefthand side of $(1)$ is

$$\left(\sum_{i=0}^{20}\binom{20}ix^i\right)\left(\sum_{j=0}^{20}\binom{20}jx^j\right)\,.\tag{4}$$

When you multiply this out, the collected $x^r$ term will be

$$\begin{align*}&\binom{20}0\binom{20}rx^{0+r}+\binom{20}1\binom{20}{r-1}x^{1+(r-1)}+\ldots\\ &\ldots+\binom{20}{r-1}\binom{20}1x^{(r-1)+1}+\binom{20}r\binom{20}0x^{r+0}\,,\end{align*}$$

whose coefficient is indeed $(2)$. The other terms that result from expanding $(4)$ contain other powers of $x$ and so don’t contribute to the $x^r$ term of the product.

Alternatively, you can interpret the sum $(2)$ combinatorially to arrive at the same result. You have a pool of $20$ men and $20$ women, and you want to form a committee of $r$ people from this pool. If you decide to have $k$ women on the committee, you must have $r-k$ men. You can choose the $r-k$ men in $\binom{20}{r-k}$ ways and the $k$ women in $\binom{20}k$ ways, so there are $\binom{20}{r-k}\binom{20}k$ ways to choose such a committee. Summing over $k$ shows that $(2)$ gives the total number of possible $r$-person committees. On the other hand, we could simply pick $r$ people from the pool of $40$ to form the committee, something that we can do in $\binom{40}r$ ways. This counts exactly the same committees and establishes the equality $(3)$ without reference to the polynomials in $(1)$. As was noted in the comments, this is an instance of the (very useful) Vandermonde identity.

Answer 2

You can choose $r$ elements from $40$ by choosing $r$ from the first $20$; or $r-1$ from the first $20$ and $1$ from the remaining $20$; or $r-2$ from the first $20$ ...

This is also reflected in the coefficients of the two different expressions $(1+x)^{20}(1+x)^{20}=(1+x)^{40}$ which collect and combine.

$\left(\binom {20}0\right)^2$ is what you get from choosing $0$ from $40$ and gives the coefficient of $1$ (ie the coefficient of $x^0$ with $r=0$)