Factors of Binomials

For discussing Olympiad Level Combinatorics problems
User avatar
sowmitra
Posts:155
Joined:Tue Mar 20, 2012 12:55 am
Location:Mirpur, Dhaka, Bangladesh
Factors of Binomials

Unread post by sowmitra » Thu Aug 16, 2012 4:27 pm

Suppose, $p$ is a prime. Show that, all the numbers in the $p^{th}$ row of the Pascal's Triangle (except $\binom{p}{0}$ and $\binom{p}{p}$) are divisible by $p$, i.e,
\[\displaystyle p\mid \binom{p}{k}\]
\[\displaystyle\forall 0<k<p\]
Last edited by sowmitra on Thu Aug 16, 2012 5:00 pm, edited 1 time in total.
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

User avatar
sowmitra
Posts:155
Joined:Tue Mar 20, 2012 12:55 am
Location:Mirpur, Dhaka, Bangladesh

Re: Factors of Binomials

Unread post by sowmitra » Thu Aug 16, 2012 4:30 pm

Lemma:
Prove that, $\displaystyle \binom{n}{r}=\frac{n}{r}\binom{n-1}{r-1}$
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

User avatar
Tahmid Hasan
Posts:665
Joined:Thu Dec 09, 2010 5:34 pm
Location:Khulna,Bangladesh.

Re: Factors of Binomials

Unread post by Tahmid Hasan » Thu Aug 16, 2012 9:36 pm

sowmitra wrote:Suppose, $p$ is a prime. Show that, all the numbers in the $p^{th}$ row of the Pascal's Triangle (except $\binom{p}{0}$ and $\binom{p}{p}$) are divisible by $p$, i.e,
\[\displaystyle p\mid \binom{p}{k}\]
\[\displaystyle\forall 0<k<p\]
$\binom{p}{k}=\frac{p!}{(p-k)!k!}$,$(p-k)!k!$ is coprime with $P \forall 0<k<p$ and $\binom{p}{k}$ is an integer,so we are done.
বড় ভালবাসি তোমায়,মা

User avatar
sowmitra
Posts:155
Joined:Tue Mar 20, 2012 12:55 am
Location:Mirpur, Dhaka, Bangladesh

Re: Factors of Binomials

Unread post by sowmitra » Thu Aug 16, 2012 10:49 pm

@Tahmid: Quite a nice and easy solution. :D It seems I have overlooked it. :P
But, I have learnt a technique which makes good use of the lemma:
We have, $\displaystyle\binom{p}{k}=\frac{p}{k}\binom{p-1}{k-1}$
Therefore,$\displaystyle k\binom{p}{k}=p\binom{p-1}{k-1}$
Now, both sides of the identity are integers.So,
$\displaystyle p\mid k\binom{p}{k}$
Since, $k<p$ and $p$ is a prime, so, $(p,k)=1$
Then, we can say, $\displaystyle p\mid\binom{p}{k}$.
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

User avatar
sowmitra
Posts:155
Joined:Tue Mar 20, 2012 12:55 am
Location:Mirpur, Dhaka, Bangladesh

Re: Factors of Binomials

Unread post by sowmitra » Fri Aug 17, 2012 5:01 pm

And here is a proof of the lemma. It's quite straightforward, actually :
We have,
$\displaystyle\binom{n}{r}=\frac{n!}{(n-r)!r!}=\frac{n.(n-1)!}{r.(n-r)!(r-1)!}=\frac{n}{r}.\frac{(n-1)!}{((n-1)-(r-1))!(r-1)!}=\frac{n}{r}\binom{n-1}{r-1}$
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

Post Reply