How to prove the binomial coefficient?

[Eclair_de_XII]

Homework Statement

"Prove that the coefficient for $x^ky^{n-k}$ is $\binom n k$."

Relevant Equations

Derived expression for binomial coefficient: $\sum_{m=1}^{n-k+1} \sum_{i=1}^m i$

Basically, the way I did this problem was to use a table with a known $n$ and $k$. In this case, I fixed $n=5$, and $k=3$. I wanted to find the number of terms with three $x$'s and two $y$'s. I labeled each $x_i$, $1\leq i \leq 5$; the $y_i$ are labeled the same way. Anyway, what I did was create a table that helped me keep count of how many possible terms I can have with exactly three $x$'s. It looks something like this: I made a matrix (table) with the indices at the top, the $k-1$ variables I fix as $X$, the possible choices for the last $x_i$ as $O$, and the variable(s) I exclude as $+$.

$\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ X & X & O & O & O \\ X & + & X & O & O \\ X & + & + & X & O\\ + & X & X & O & O \\ + & X & + & X & O \\ + & + & X & X & O \\ \end{pmatrix}$

What I do is count the number of $O$'s there are to get the number of terms with exactly $k$ $x_i$ in them. I get that this is not exactly orthodox, but that is how I got the expression in the relevant equations section. The trouble I have is, that I am not sure that it is completely correct, and that I am having trouble equating it to $\binom n k$. I imagine it will take a lot of strenuous algebra, which is why I want to hold off on it until someone can confirm my suspicions that:

$\binom n k = \sum_{m=1}^{n-k+1} \sum_{i=1}^m i$

 

[timetraveller123]

one other way i would recommend is induction did you consider that?

edit:(i just realized this)
or alternatively you could get a much faster solution if you consider what it means to get a term of
$x^k y^{n-k}$
and it relation to choosing
trying writing
$(x+y)^n$
as
$(x+y)(x+y)...(x+y)$

 

[member 587159]

Use induction or use a counting argument:

In the expansion of $(x+y)^n= (x+y)\dots (x+y)$, in how many ways can we get the term $x^ky^{n-k}$?

 

[Dick]

$\binom n k = \sum_{m=1}^{n-k+1} \sum_{i=1}^m i$

That is certainly untrue just by inspection. It's saying that $\binom n k$ only depends on $n-k$.

 

[vela]

$\binom n k = \sum_{m=1}^{n-k+1} \sum_{i=1}^m i$

You could check your attempt with other values of $n$ and $k$, and you'll see it doesn't work in general. Plus you'll probably recognize @Dick's observation about your result depending only on $n-k$.

I think your analysis just happened to work for that specific case because $k=3$, but if you consider a case where $k=4$ for example, the counting gets a bit more complicated.