1
$\begingroup$

Let $n>1$ be an odd integer.

Show that there is an odd number of odd numbers in the sequence: $\binom{n}{1}, \binom{n}{2}, \binom{n}{3}, ..., \binom{n}{\frac{n-1}{2}}$

I've tried doing it by separating the problem into two cases, one in which $n=4k+1$ and one in which $n=4k+3$ where $k$ is a full number. Then by supposing that $\binom{n}{i}$ is either even or odd for a given $i$, then by writing $\binom{n}{i+1}$ as $\frac{\binom{n}{i}}{i+1} (n-i)$ in order to determine the parity of $\binom{n}{i+1}$. I didn't get anywhere.

Could someone please help me? Thanks.

$\endgroup$
3
  • $\begingroup$ Sorry, n>1. Lemme fix that. $\endgroup$ Commented Mar 5 at 2:02
  • $\begingroup$ Ignoring $n=1$, show that $\sum_{k=1}^{(n-1)/2} \binom nk$ is an odd sum. If the contrary that there are even number of odd terms (plus any number of even terms), the sum would be even. $\endgroup$
    – peterwhy
    Commented Mar 5 at 2:04
  • $\begingroup$ Didn't think of that. Thank you very much! $\endgroup$ Commented Mar 5 at 2:17

1 Answer 1

1
$\begingroup$

Ignoring $n=1$, the sum $\sum_{k=1}^{(n-1)/2} \binom nk$ is an odd sum:

$$\begin{align*} \sum_{k=0}^{n} \binom nk &= 2^n\\ \sum_{k=0}^{(n-1)/2} \binom nk &= 2^{n-1}\\ \sum_{k=1}^{(n-1)/2} \binom nk &= 2^{n-1} -1\\ &\equiv 1\pmod2 \end{align*}$$

If the contrary that there are even number of odd terms (plus any number of even terms), the sum would be even:

$$\begin{align*} \sum_{k=1}^{(n-1)/2} \binom nk &\equiv \left(\text{# of odd terms}\right)\cdot 1 + \left(\text{# of even terms}\right)\cdot 0 &&\pmod 2\\ \left(\text{# of odd terms}\right) &\equiv 1 &&\pmod2 \end{align*}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .