Proof that combinations are equal to coefficients in the binomial expansion

Question

Let $n\in N$, $k\in Z$, $o\leq k \leq n$. Define $C^{n}_k$ as the coefficient of $x^{n-k}y^k$ in the expansion of $(x+y)^n$

$$(x+y)^n= \sum^{n}_{k=0} C^{n}_k x^{n-k}y^k$$

Prove that ${C^{n}_{k}}={n \choose k}$.

My first guess is to use Pascal's triangle.

Answer 1

This depends on your definition of $\binom{n}{k}.$ If it is defined as the number of subsets of size $k$ from a set of size $n,$ then just look at the product $$(x+y)^n=(x+y)(x+y) \cdots (x+y)$$ where there are $n$ copies of $(x+y)$ to be multiplied. When expanded, how many terms will have $k$ copies of $y$ and so the remaining $n-k$ copies of $x$? So the number of these terms is $\binom{n}{k}.$

Added example:

Here is an explanatory example for $(x+y)^5.$ First one needs to use a generalized distributive law which for example allows one to go from $(a+b)(c+d)(e+f)$ directly to the 8 possible products $$ace+acf+ade+adf+bce+bcf+bde+bdf.$$ In other words one takes one term from each factor in all possible ways, and multiplies those terms. Note I have intentionally kept the order in the terms multiplied, e.g. did not write $cae$ rather than $ace.$

Now IF the multiplication is commutative, one can interchange the factors in the terms after use of the generalized distributive law. But it is instructive to wait on doing this. For our example of $(x+y)^5$ there will then be 32 terms in all after applying the generalized distributive law. Among these terms, those containing two $y$'s will be $yyxxx,yxyxx,\cdots,xxxyy,$ and there are ten in all, going with $\binom{5}{2}$ Concretely, the subset $\{3,5\}$ of the five element set $\{1,2,3,4,5\}$ would be taken to mean that the two $y$'s appear in positions 3 and 5, i.e. $\{3,5\}$ would go with the term $xxyxy.$

Now in showing the rest of the binomial theorem, all that is done is that in each term one uses commutativity to place all the $x$'s before the $y$'s, so that our specific term $xxxyy$ would be counted toward the coefficient of $x^3y^2.$ As we have explained, there are ten terms which would contribute to this count, which makes $10=\binom{5}{2}$ for the coefficient of $x^3y^2.$

Answer 2

We can write $(x+y)^n$ as $(x+y)(x+y)(x+y)\cdots \quad n\text{ times}$, i.e. $$(x \text{ or } y)\cdot(x \text{ or } y)(x \text{ or }y)\cdots \quad n \text{ times}$$

i.e. its a string of length $n$ having $x$ and $y$ as its alphabets.Now we have to find coefficient of $x^{n-k}y^k$ i.e. any $n$-length combination having $k$, $y$'s and the remaining $(n-k)$ ,$x$'s ; so finding the coefficient is equivalent to the question:-
"In how many ways we can select $k$ , $y$'s and
remaining $n-k$ , $x$'s out of a box containing $n$ ,($x$or $y) $'s"
the answer is $C_k^n= \dbinom {n}{k}$

Answer 3

I show a proof based on induction below. Hope it helps.

---

Basis. Since $$ (x + y)^1 = x + y = C^1_0x^1y^0 + C^1_1x^0y^1 = C^1_0x + C^1_1y\text{,} $$ we have $$ C^1_0 = 1 = {1 \choose 0}\quad \text{and}\quad C^1_1 = 1 = {1 \choose 1}. $$ We therefore have proved that when $n = 1$, ${n \choose k} = C^n_k$ for $0 \leq k \leq n$.

Induction. Now suppose for some $n \geq 1$, ${n \choose k} = C^n_k$ for any $0 \leq k \leq n$. We want to prove that ${n + 1\choose k} = C^{n+1}_k$ for any $0 \leq k \leq n + 1$. Below is the detail.

\begin{align} (x+y)^{n+1} &= (x + y)\cdot(x + y)^n \\ & =(\color{red}{x}+\color{blue}{y})\cdot\sum_{k=0}^n {n \choose k}x^{n-k}y^k \\ & = \color{red}{x\cdot\sum_{k=0}^n{n\choose k}x^{n-k}y^k} + \color{blue}{ y\cdot\sum_{k=0}^n{n\choose k}x^{n-k}y^k} \\ & = \color{red}{\sum_{k=0}^n{n\choose k}x^{n-k+1}y^k} + \color{blue}{\sum_{k=0}^n{n\choose k}x^{n-k}y^{k+1}} \\ & = \color{red}{\sum_{k=0}^n{n\choose k}x^{n+1-k}y^k} + \color{blue}{\sum_{k=1}^{n+1}{n\choose k - 1}x^{n + 1 -k}y^{k}} \\ \end{align} Therefore,

• the coefficient for the term $x^{n+1-0}y^0$ is ${n \choose 0} = {{n+1} \choose 0}$

• the coefficient for the term $x^{n+1-k}y^k$ ($1 \leq k \leq n$) is ${n \choose k} + {n \choose k - 1} = {n + 1 \choose k}$

• the coefficient for the term $x^0y^{n+1}$ is ${n \choose n} = {n + 1 \choose n + 1}$

We conclude that ${n + 1 \choose k} = C_k^{n+1}$ for $\forall 0 \leq k \leq n + 1$.