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\]
Factors of Binomials:Part 2
Re: Factors of Binomials:Part 2
Hint:
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
- Tahmid Hasan
- Posts:665
- Joined:Thu Dec 09, 2010 5:34 pm
- Location:Khulna,Bangladesh.
Re: Factors of Binomials:Part 2
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
Some more examples BdMO Higher Secondary 9
CGMO-2012-8
বড় ভালবাসি তোমায়,মা
Re: Factors of Binomials:Part 2
Oh, yes! Lucas definitely kills it. But, it seems a little brute force to me.
How about using the lemma in Mahi's link....?
How about using the lemma in Mahi's link....?
Re: Factors of Binomials:Part 2
My solution needs to be checked again,because I often make mistakes! 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.
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!}}$
Re: Factors of Binomials:Part 2
@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}$
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}$