How to prove the binomial coefficient?

  • #1
837
50

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##
 

Answers and Replies

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

edit:(i just realised 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)
##
 
Last edited:
  • #3
Math_QED
Science Advisor
Homework Helper
2019 Award
1,748
752
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}##?
 
  • #4
Dick
Science Advisor
Homework Helper
26,260
619
##\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##.
 
  • #5
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,813
1,391
##\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.
 

Related Threads on How to prove the binomial coefficient?

Replies
5
Views
765
  • Last Post
Replies
23
Views
4K
Replies
2
Views
1K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
762
  • Last Post
Replies
6
Views
4K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
2
Views
1K
Top