Теоретико-числовые свойства биномиальных коэффициентов

(a) Заметим, что Тогда

Теперь заметим, что

Раскроем скобки и перегруппируем слагаемые с плюсом и с минусом. Тогда сумма слагаемых с плюсом равна

Сумма слагаемых с минусом равна

Тогда исходная сумма равна:

(b) Заметим, что

Поймем, какую комбинаторную задачу решает выражение в скобке. Для этого расположим в ряд шаров. — число способов выбрать шаров из этого ряда так, что сначала выбраны шаров из первых а затем еще из оставшихся Таким образом, сумма в скобке — это число способов вставить перегородку в наш ряд так, что слева и справа от нее не менее шаров, а затем выбрать по шаров с каждой стороны.

Эта задача эквивалентна тому, чтобы найти число способов в ряде из шара выбрать а затем средний заменить перегородкой. Тогда сумма из скобки равна Таким образом,