MathDB

when binomial is odd then we have a power of 2

Source: Nordic Mathematical Contest 1998 #4

October 3, 2017

combinatoricsbinomial coefficientsmodular arithmetic

Problem Statement

Let

n

be a positive integer. Count the number of numbers

k \in \{0, 1, 2, . . . , n\}

such that

\binom{n}{k}

is odd. Show that this number is a power of two, i.e. of the form

2^p

for some nonnegative integer

p