Prove that ${2^n-1\choose k}$ and ${2^n-k\choose k}$ ar always odd. 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)$
 A: 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$.
A: 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$.
A: 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.
A: 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.
A: $$\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.
A: 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:


*

*Chu–Vandermonde identity:
$${r\choose s}=\sum_{j=0}^{s}{{m\choose j}}{r-m\choose s-j}\label{eqcv}\tag{1}$$

*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.
A: 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.
