How to prove the binomial coefficient?

In summary, the conversation discusses a problem solving method that involves creating a table to count the number of terms with specific variables. The method is not considered orthodox but has been used to get the expression in the relevant equations section. However, there are doubts about its accuracy and an alternative solution involving induction is suggested. It is also pointed out that the original method does not work for all values of n and k.##
  • #1
Eclair_de_XII
1,083
91
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##
 
Physics news on Phys.org
  • #2
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)
##
 
Last edited:
  • #3
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
Eclair_de_XII said:
##\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
Eclair_de_XII said:
##\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 to How to prove the binomial coefficient?

1. What is the binomial coefficient?

The binomial coefficient, also known as the "choose" function, is a mathematical concept used to calculate the number of ways to choose a subset of objects from a larger set. It is denoted by the symbol "n choose k" or nCk.

2. How do you prove the binomial coefficient formula?

The binomial coefficient formula can be proven using mathematical induction or by using combinatorial arguments. The most common proof method is using Pascal's triangle, which demonstrates the pattern of the coefficients.

3. What is the relationship between the binomial coefficient and the binomial theorem?

The binomial theorem is a formula that expands the power of a binomial expression, while the binomial coefficient is the numerical value of each term in the expanded expression. The binomial coefficient is used to determine the coefficients in the binomial theorem.

4. Can the binomial coefficient be negative?

No, the binomial coefficient cannot be negative. It is defined as a positive integer, representing the number of ways to choose a subset from a larger set. If the result of the calculation is a negative number, it means that the subset cannot be formed.

5. How is the binomial coefficient used in real-life applications?

The binomial coefficient has many applications in various fields such as statistics, probability, and engineering. It is used to calculate the probability of certain outcomes in experiments and to determine the coefficients in polynomial expansions. It also has applications in computer science, particularly in the analysis of algorithms.

Similar threads

  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus and Beyond Homework Help
Replies
14
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
873
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
390
  • Calculus and Beyond Homework Help
Replies
3
Views
532
  • Calculus and Beyond Homework Help
Replies
1
Views
622
  • Calculus and Beyond Homework Help
Replies
1
Views
362
  • Calculus and Beyond Homework Help
Replies
15
Views
2K
  • Calculus and Beyond Homework Help
Replies
18
Views
1K
Back
Top