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

Сразу домножим наше тождество на То есть будем доказывать, что

Предположим, что у нас в ряд стоят человек. И мы хотим выбрать из них хотя бы человека. Понятно, что каждому такому выбору соответствует выбор, в котором меньше человека (просто выбрать тех, кого не выбрали в первом способе). Тогда всего таких вариантов ровно Посчитаем требуемое количество способов по-другому. Посмотрим, где может находиться -ый человек (считая слева направо). Пусть он находится на месте, где Тогда среди первых человек у нас есть ровно способов выбрать человек. А среди оставшихся человек мы можем выбирать любых людей, то есть способов. Итого, если -ый по счету человек стоит на -ом месте, то всего вариантов Сложив способы по всем получаем требуемое равенство.