A quick question on coefficient of binomial expansion

In summary, the conversation is discussing the proof of a theorem stating that for integers n and i, where 0 <= i <= n, nCi is always an integer. The proof involves expanding (x+y)^n and showing that the coefficient of xiyn-i is always an integer. The conversation then moves on to discussing the proof of another theorem, which states that for a prime number p, p divides C(mp,r) where r is an integer not divisible by p. The conversation includes a detailed proof involving the division algorithm and residue classes.
  • #1
AlbertEinstein
113
1
Is it always necessary that C(n,r) is an integer if n and r are integers ?
Is there any proof ?Please clarify.

thanks.
 
Physics news on Phys.org
  • #2
If the above statement is trivial, does the following theorem requires a proof:

Th: Prove that p divides C(mp,r) where p is a prime and r is an integer not divisible by p.
 
  • #3
Yes, nCi is always an integer (for n, i integers and 0<= i<= n). One proof is to note that nCi is the coefficient of xiyn-i in (x+ y)n- which is necessarily an integer.

I would not say that that was "trivial" and certainly would expect a proof of the theorem you give.
 
Last edited by a moderator:
  • #4
Well then for the proof is it enough to write that
C(mp,r) = (mp)! / (r!) (mp-r)!
= mp(mp-1)(mp-2)../ (r!) (mp-r)!
= p*an integer

Therefore p divides C(mp,r).
 
  • #5
AlbertEinstein said:
If the above statement is trivial, does the following theorem requires a proof:

Th: Prove that p divides C(mp,r) where p is a prime and r is an integer not divisible by p.

[tex]C(mp,r) = \frac{(mp)!}{(mp-r)!r!} = C(n,i)[/itex] where mp = n and i = r. So long as r greater than or equal to zero and less than or equal to mp you clearly get an integer by the basic construction. In fact this coefficient has to happen for one of the term's in the expansion of [itex](x+1)^{mp}[/itex]. So you have an integer and now you want to know whether it is divisible by p? Think about expanding it and writing each factor in the numerator and denominator in the form pa+r. Notice that there must be m factors in the numerator that are divisible by p. The number of factors in the denominator divisible by p are related like this

[tex]Div(r,p)+ Div(mp-r,p) < m \leftrightarrow Mod(r,p)\neq0[/tex]

Just simply count them if Div(r,p) = 4 and Mod(r,p) > 0 then subtracting r from mp removes the factors mp, (m-1)p, (m-2)p, (m-3)p, (m-4)p. So there were m factors divisible by p in mp!, in (mp-r)! there are m-5 the sum of m-5 and 4 is m-1 factors in the denominator to cancel the m factors in the numerator. C(mp,r) is divisible by p unless Mod(r,p)=0 ie r is divisble by p, so the answer to your question is yes the statement is true. However I do not think it is obvious from the first statement you made. We can get at this more obviously by the following

[tex]Div(mp,p)=Div(r+(mp-r),p) =Div(r,p)+ Div(mp-r,p)+\{0,1\}[/tex]
[tex]m-\{0,1\} =Div(r,p) + Div(mp-r,p)[/tex]

Residues are not completely obliterated by the Div operator, they survive as elements of the set {0,1}. We could give such sets the name case identifier sets or case sets. The only way for case = 1 to hold is for there to be residues of both r and mp-r modulo p, that is r and p are coprime.
 
Last edited:
  • #6
Hey playdo,I understood only the first paragraph.I showed that C(mp,r) is a multiple of p and hence the theorem follows.Does my proof lack something? I didn't understand what Div is .Could you explain in some more basic terms?

Thanks.
 
  • #7
Hey everyone, please help me.:frown:
 
  • #8
AlbertEinstein said:
Hey playdo,I understood only the first paragraph.I showed that C(mp,r) is a multiple of p and hence the theorem follows.Does my proof lack something? I didn't understand what Div is .Could you explain in some more basic terms?

Thanks.

Div(a,p) means integer division of a by p. Mod(a,p) is a related function it means the remainder after dividing a by p. The following statement is true generally and is called the division algorithm

a = aDiv(a,p)+Mod(a,p)

Mod(a,p) is alos sometimes written as a Mod p. I prefer the function notation. Your theroem is true and I gave a proof because I think one was required and it was interesting.

Does that help? :smile:

If it doesn't don't worry about it. I am wondering what I was drinking that night myself. When I wrote it, it was as clear as a bell to me. No it works write this

[tex]Div(r,p)+Div(mp-r,p) = \frac{r-Mod(r,p)}{p}+\frac{mp-r -Mod(mp-r,p)}{p}[/tex]

No if p divides r then Mod(r,p)=Mod(mp-r,p) = 0 so this last becomes

[tex]r/p + m - r/p = m[/tex]

If p does not divide r this becomes

[tex]r/p + m - r/p -(Mod(r,p)+Mod(mp-r,p))/p = m-1[/tex]

That should help.
 
Last edited:

1. What is the coefficient of binomial expansion?

The coefficient of binomial expansion refers to the numerical value that appears in front of the variables in a binomial expression when it is expanded. It is calculated using the binomial coefficient formula, which takes into account the number of terms, the power of each term, and the order of the expansion.

2. How is the coefficient of binomial expansion calculated?

The coefficient of binomial expansion is calculated using the binomial coefficient formula, which is nCr, where n is the total number of terms and r is the power of the term being evaluated. This formula can also be written as n! / (r! * (n-r)!), where ! represents the factorial function.

3. What is the significance of the coefficient of binomial expansion?

The coefficient of binomial expansion is significant because it represents the number of ways a specific term can be obtained when a binomial expression is expanded. It also helps in simplifying complicated calculations and identifying patterns in the expansion.

4. Can the coefficient of binomial expansion be negative?

No, the coefficient of binomial expansion cannot be negative. This is because the binomial coefficient formula takes into account the number of ways a term can be obtained, which is always a positive value. However, the term itself may be negative depending on the expression being expanded.

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

The coefficient of binomial expansion is used in various fields such as statistics, probability, and computer science. It is used to calculate the probability of certain events, analyze data, and simplify complicated mathematical expressions. It is also used in computer algorithms, specifically in combinatorial problems and in generating random numbers.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
3
Views
139
  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Linear and Abstract Algebra
Replies
8
Views
995
  • Calculus
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
5
Views
177
  • Linear and Abstract Algebra
Replies
4
Views
3K
  • Calculus and Beyond Homework Help
Replies
14
Views
2K
Replies
1
Views
907
Replies
12
Views
827
Back
Top