Online Course Discussion Forum

math challenge II-A Combinatorics Problem 6.10

 
 
Picture of John Lensmire
Re: math challenge II-A Combinatorics Problem 6.10
by John Lensmire - Friday, September 24, 2021, 1:39 PM
 

For these with variables, it is often pretty helpful to think about specific examples. Let's look at $n=3$.

The idea is that we want to find the coefficient of $x^3$ in $(1+x)^6$.

Method 1: Just using the binomial theorem this is $\displaystyle \binom{6}{3}$. (Note this would be $\displaystyle \binom{2n}{n}$ in general.)

Method 2: We can write $(1+x)^6 = (1+x)^3\cdot (1+x)^3$ and find the coefficient after multiplying. Note: This is not the easiest way to find the coefficient, but will help us prove our identity. We have $$(1+x)^3\cdot (1+x)^3 = \left( \binom{3}{0} x^3 + \binom{3}{1} x^2 + \binom{3}{2} x + \binom{3}{3} \right) \cdot \left( \binom{3}{0} x^3 + \binom{3}{1} x^2 + \binom{3}{2} x + \binom{3}{3} \right)$$ There are $4$ ways to multiply these terms to get $x^3$: $$\binom{3}{0} x^3\cdot \binom{3}{3}, \binom{3}{1} x^2\cdot \binom{3}{2} x, \binom{3}{2} x\cdot \binom{3}{1} x^2,  \binom{3}{3} \cdot \binom{3}{0} x^3,$$ so the coefficient of $x^3$ can also be written as: $$\binom{3}{0} \cdot \binom{3}{3} + \binom{3}{1} \cdot \binom{3}{2} + \binom{3}{2} \cdot \binom{3}{1} + \binom{3}{3} \cdot \binom{3}{0}$$ which by symmetry is equal to $$\binom{3}{0}^2 + \binom{3}{1}^2 + \binom{3}{2}^2 + \binom{3}{3}^2.$$ Therefore, $$\binom{6}{3} = \binom{3}{0}^2 + \binom{3}{1}^2 + \binom{3}{2}^2 + \binom{3}{3}^2$$ as needed.

Try to write thinks out for $n=4$ or $n=5$ to make sure you can understand the pattern.