Prove that ${2^n-1\choose k}$ and ${2^n-k\choose k}$ ar always odd.

Question

How can I prove that ${2^n-1\choose k}$ and ${2^n-k\choose k}$ always returns odd numbers? It is possible to prove this by congruence?

by the way : $0 \leq k \leq (2^n-1)$

Answer 1

$$\binom{2^n-1}{k} = \frac{(2^n-1)(2^n-2)(2^n-3)\cdots(2^n-k)}{1\cdot 2\cdot 3\cdots k} $$ and $2^n-a$ is divisible by exactly as many factors of $2$ as $a$ is.

This means that every factor of $2$ in the numerator is matched by a factor of $2$ in the denominator. After cancelling those, what's left in the numerator must be an odd number, and you can't get an even integer by dividing an odd integer by any integer.

Answer 2

Kummers theorem:

The maximum power of the prime $p$ that divides $\binom{n}{k}$ is equal to the number of carries when adding $n-k$ and $k$ in base $p$.

Clearly if $a$ and $b$ add up to $111\dots 1$ in binary there can't be any carries, since the digit in the position of the first carry is always $0$.

Answer 3

See Lucas's theorem on binomial coefficients. More generally, for any prime $p$, $\displaystyle {{p^n-1} \choose k}$ is never divisible by $p$ when $0 \le k \le p^n-1$.

Answer 4

In formula $(7)$ of this answer, it is shown that the number of factors of $p$ in $\binom{n}{k}$ for a prime $p$ is $$ \frac{\sigma_p(k)+\sigma_p(n-k)-\sigma_p(n)}{p-1}\tag{1} $$ where $\sigma_p(k)$ is the sum of the digits in the base-$p$ expansion of $k$. This is also the number of carries performed when adding $n-k$ and $k$ in base-$p$. Since all the base-$2$ digits of $2^n-1$ are $1$, $k$ and $2^n-1-k$ are one's complements and so the sum of all their digits will be the sum of the digits of $2^n-1$ (which is $n$).

Therefore, by $(1)$, the number of factors of $2$ in $\binom{2^n-1}{k}$ is $0$. That is, $\binom{2^n-1}{k}$ is odd.

Answer 5

For a completely different approach, you can prove it by induction on $n$ if you first prove, also by induction on $n$, that $\binom{2^n}k$ is odd if and only if $k=0$ or $k=2^n$. Assume this result for $n$. By Vandermonde’s identity we have

$$\binom{2^{n+1}}k=\sum_{\ell=0}^{2^n}\binom{2^n}\ell\binom{2^n}{k-\ell}\;,\tag{1}$$

where by symmetry we may assume that $k\le 2^n$. The $\ell$ term in the summation in $(1)$ is odd if and only if $\binom{2^n}\ell$ and $\binom{2^n}{k-\ell}$ are both odd, which by the induction hypothesis is the case if and only if $\ell=k=0$, $\ell=0$ and $k=2^n$, or $\ell=k=2^n$. Thus, $\binom{2^{n+1}}k$ is even if $0<k<2^n$,

$$\binom{2^{n+1}}{2^n}\equiv\binom{2^n}0\binom{2^n}{2^n}+\binom{2^n}{2^n}\binom{2^n}0\equiv 0\pmod2\;,$$

and

$$\binom{2^{n+1}}0\equiv\binom{2^n}0^2+\binom{2^n}0\binom{2^n}{2^n}+\binom{2^n}{2^n}\binom{2^n}0\equiv 1\pmod2\;,$$

as desired.

Now assume the actual desired result for $n$. By Vandermonde’s identity we have

$$\binom{2^{n+1}-1}k=\sum_{\ell=0}^{2^n}\binom{2^n}\ell\binom{2^n-1}{k-\ell}\;,$$

where by symmetry we may assume that $k<2^n$. By the induction hypothesis $\binom{2^n-1}{k-\ell}$ is odd for each $\ell\le k$, so

$$\binom{2^n}\ell\binom{2^n-1}{k-\ell}\equiv\binom{2^n}\ell\pmod2$$

for each $\ell\le k$, and

$$\binom{2^{n+1}-1}k\equiv\sum_{\ell=0}^k\binom{2^n}\ell\pmod2\;.\tag{2}$$

From the preliminary result we know that $\binom{2^n}\ell$ is even for $1\le\ell\le k$ (since $k<2^n$), so the only odd term in the summation in $(2)$ is $\binom{2^n}0=1$, and $\binom{2^{n+1}-1}k$ is odd.

Answer 6

For the first proposition, i.e., "$2^n-1\choose k$ is odd", I came up to a proof by mathematical induction and using some basic properties of binomial coefficient ${r\choose s}$. The other proposition "$2^n-k\choose k$ is odd" is not true (consider $n=k=3$).

The aforementioned properties are:

1. Chu–Vandermonde identity: $${r\choose s}=\sum_{j=0}^{s}{{m\choose j}}{r-m\choose s-j}\label{eqcv}\tag{1}$$
2. Pascal's rule: $${r\choose s}={r-1\choose s}+{r-1\choose {s-1}}\label{eqpascal}\tag{2}$$

Here is the proof. Obviously, the proposition is true for $n=1$. Assuming it to be true for a natural number $n$, we have to show it is also true for $n+1$, i.e., ${2^{n+1}-1\choose k}$ is odd for $k=0,1,\dots,2^{n+1}-1$.

To do this, we start from (\ref{eqcv}) and let $r=2^{n+1}-1$, $s=k$, and $m=2^n-1$. Also we first assume $0\leq k\leq 2^n-1$. So: $${2^{n+1}-1\choose k}=\sum_{j=0}^{k}{{2^n-1\choose j}}{2^n\choose k-j}$$ which after taking out the last term (the term with $j=k$) leads to: $${2^{n+1}-1\choose k}={2^n-1\choose k}+\sum_{j=0}^{k-1}{{2^n-1\choose j}}{2^n\choose k-j}\label{eq3}\tag{3}$$

Now, according to the induction hypothesis, ${2^n-1\choose k}$ and ${2^n-1\choose j}$ are odd numbers. Thus, we just need to show ${2^n\choose k-j}$ is even. By using (\ref{eqpascal}) and letting $r=2^n$ and $s=k-j$ we have: $${2^n\choose k-j}={{2^n-1}\choose k-j}+{{2^n-1}\choose k-j-1}$$

which is the sum of two odd numbers (induction hypothesis), and hence, it's even. Notice that the assumption $0\leq k\leq 2^n-1$ together with $j\leq k-1$, results in: $$2^n-1\geq k-j\geq k-j-1\geq0$$ which satisfies the desired limits for using binomial coefficients.

The last step is to show the proposition is also true for $2^{n+1}-1\geq k>2^n-1$. In such cases, we define $k'=2^{n+1}-1-k$, which leads to $0\leq k'<2^n$, or equivalently $0\leq k'\leq 2^n-1$ which is the same as the limit we first considered for $k$. Since ${2^{n+1}-1\choose{k}}={2^{n+1}-1\choose{k'}}$ (due to symmetry), we can repeat the proof, this time with $k$ replaced by $k'$. The proof is now complete.

Answer 7

Everything in row $2^n - 1$ of Pascal's triangle is odd because everything in row $2^n$ is even except for the two ends.