On a past-paper of a Combinatorics exam I will be taking they ask the question:

Prove that for $k$ odd and greater than 1, the sequence of numbers

$\binom{k}{1}, \binom{k}{2}, ..., \binom{k}{\frac{k-1}{2}}$

has an odd number of odd numbers.

I was wondering if anyone has any elegant solutions to the question posted above. I have my own solution which is as such:

For $k$ odd and greater than 1, $\binom{k}{1}, \binom{k}{2}, ..., \binom{k}{\frac{k-1}{2}}$ has an odd number of odd numbers if and only if the sum $\binom{k}{1} + \binom{k}{2} + ... + \binom{k}{\frac{k-1}{2}}$ is odd. Using Pascals identity this sum can be written as: $\binom{k-1}{0} + 2\left(\binom{k-1}{1} + \binom{k-1}{2} + ...\binom{k-1}{\frac{k-3}{2}} \right) + \binom{k-1}{\frac{k-1}{2}}$.

From here we know the first term of the sum $\binom{k-1}{0} = 1$ is odd, the middle term is clearly even so just need to show $\binom{k-1}{\frac{k-1}{2}}$ is even to be done. Since $k$ is odd, $k-1$ is even so let $k-1 = n$ where $n$ is even. Need to show $\binom{n}{\frac{n}{2}}$ even.

This result comes immediately from the fact that: $\binom{n}{0} + \binom{n}{1} + ... + \binom{n}{n} = 2\left(\binom{n}{0} + \binom{n}{1} + ... + \binom{n}{\frac{n-1}{2}}\right) + \binom{n}{\frac{n}{2}} = 2^n$ for $n$ even.

I think this solution is correct but am sure someone out there can do better!


1 Answer 1


Your basic idea is very nice, but the details can be simplified. By symmetry, if $k$ is odd we have $$\binom{k}{0}+\binom{k}{1}+\binom{k}{2}+\cdots+\binom{k}{(k-1)/2}=2^{n-1}.$$

It follows that your sum is $2^{n-1}-1$.


You must log in to answer this question.

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