I was going through a paper where I stuck on a combinatorial argument as follows
I want help with the first assertion i.e proving the inequality $\alpha(m+l)\le\alpha(m)$. As the author suggests it is very easy, I still could not figure this out although the rest of the argument was clear.
Kindly give your valuable suggestions thanks and regards in advance.
Lucas theorem says that $$\binom{m}{\ell}\equiv \prod _{i=1}^N\binom{m_i}{\ell _i}\pmod 2,$$ where $m_i$ and $\ell _i$ are the bits on the binary decomposition of $m$ and $\ell$ respectively. This implies that $m_i\geq \ell _i$ for all $i$. Let $J=\{i: m_i=\ell _i =1\}$. If $J=\emptyset $, then $\ell = 0$ so you are done. If not, then either $i+1\in J$ or not: for the former, you would eliminate at least two zeros and recover one, so $\alpha (m+\ell)<\alpha (m)$. For the later you are replacing the one. Morally, if you get a bit $=0$, you recover at most one bit on the addition.
