<s>[INST] 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)$
 [/INST] 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.
</s>