Factors of Binomials:Part 2

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:Part 2

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

Prove that, all the numbers in the $2^k-th$ row of the Pascal's Triangle, except the end one's, are even, i.e,
\[\displaystyle2\mid\binom{2^k}{r}\]
\[\displaystyle\forall 0<r<2^k\]
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: Factors of Binomials:Part 2

Unread post by *Mahi* » Fri Aug 17, 2012 9:20 am

Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

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

Re: Factors of Binomials:Part 2

Unread post by Tahmid Hasan » Fri Aug 17, 2012 7:18 pm

For these kinds of problems regarding divisibility of binomial co-efficients by primes,they are immediately killed by Lucas' Theorm.
Some more examples BdMO Higher Secondary 9
CGMO-2012-8
বড় ভালবাসি তোমায়,মা

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

Re: Factors of Binomials:Part 2

Unread post by sowmitra » Fri Aug 17, 2012 7:54 pm

Oh, yes! Lucas definitely kills it. :) But, it seems a little brute force to me. :?
How about using the lemma in Mahi's link....?
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

User avatar
SANZEED
Posts:550
Joined:Wed Dec 28, 2011 6:45 pm
Location:Mymensingh, Bangladesh

Re: Factors of Binomials:Part 2

Unread post by SANZEED » Sat Aug 18, 2012 12:27 am

My solution needs to be checked again,because I often make mistakes! :D And I took $i$ instead of $r$.
Total power of $2$ in $(2^{k})!$ is $\sum_{m=1}^{k}\left \lfloor \frac{2^{k}}{2^{m}}\right \rfloor$.
Similarly total power of $2$ in $i!$ is $\sum_{m=1}^{k}\left \lfloor \frac{i}{2^{m}}\right \rfloor$,
and total power of $2$ in $(2^{k}-i)!$ is $\sum_{m=1}^{k}\left \lfloor \frac{2^{k}-i}{2^{m}}\right \rfloor$, Because $i$ and $2^{k}-i$ can't be divided by higher power of $2$ than $2^{k}$ since $i<k$.
Now,clearly,$\sum_{m=1}^{k}\left \lfloor \frac{2^{k}}{2^{m}}\right \rfloor=\sum_{m=1}^{k}2^{k-m}=2^{k}-1$.
On the other hand,$\sum_{m=1}^{k}\left \lfloor \frac{2^{k}-i}{2^{m}}\right \rfloor=\sum_{m=1}^{k}\left \lfloor \frac{2^{k}}{2^{m}}-\frac{i}{2^{m}}\right \rfloor=\sum_{m=1}^{k}\left \lfloor 2^{k-m}-\frac{i}{2^{m}}\right \rfloor=\sum_{m=1}^{k}2^{k-m}+\sum_{m=1}^{k}\left \lfloor -\frac{i}{2^{m}}\right \rfloor$ ,by theorem $2.1.2$ of "Number Theory" by S.G. Telang. Now there is at least one $m$ for which $\frac{i}{2^{m}}$ is not an integer. So, again by the help of theorem $2.1.5$ of the same book,$\sum_{m=1}^{k}2^{k-m}+\sum_{m=1}^{k}\left \lfloor -\frac{i}{2^{m}}\right \rfloor< \sum_{m=1}^{k}\left \lfloor \frac{i}{2^{m}}\right \rfloor+\sum_{m=1}^{k}2^{k-m}-\sum_{m=1}^{k}\left \lfloor \frac{i}{2^{m}}\right \rfloor=2^{k}-1$. This means the total power of $2$ in the numerator of $2^{k}\choose i$ is greater than the total power of $2$ in the denominator. So $2^{k}\choose i$ must be even.
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

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

Re: Factors of Binomials:Part 2

Unread post by sowmitra » Sat Aug 18, 2012 5:41 pm

@Sanzeed: Wow, a truly analytic and extensive solution. :) As far as it seems to me, there aren't any mistakes.
Here's a solution using the lemma:$\displaystyle\binom{n}{r}=\frac{n}{r}\binom{n-1}{r-1}$
Suppose, $r=2^s.m$, where, $0<s<k$(since;$r<2^k$), and, $m$ is an odd number.
Now, from the lemma, we have,
$\displaystyle\binom{2^k}{r}=\frac{2^k}{r}\binom{2^k-1}{r-1}=\frac{2^k}{2^sm}\binom{2^k-1}{r-1}=\frac{2^{k-s}}{m}\binom{2^k-1}{r-1}$
So, finally we have,
$\displaystyle\binom{2^k}{r}=\frac{2^{k-s}}{m}\binom{2^k-1}{r-1}$
$\displaystyle\rightarrow m\binom{2^k}{r}=2^{k-s}\binom{2^k-1}{r-1}$
Now, both sides of this identity are integers. So, we can say,
$\displaystyle2^{k-s}\mid m\binom{2^k}{r}$
Since, $m$ is odd, we have, $(2^{k-s},m)=1$
Therefore, $\displaystyle2^{k-s}\mid\binom{2^k}{r}$. As, $k>s$ and both are non-negative integers, $(k-s)$ is at least $1$.
So, we can say, $\displaystyle2\mid\binom{2^k}{r}$
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

Post Reply