1. База индукции. При наша формула очевидна: Следовательно, формула верна при

2. Шаг индукции. Пусть мы установили истинность формулы биному при всех от до Докажем её тогда для :

Причём отметим, что в нашей записи биномиального коэффициента или или то мы считаем по определению, что такой биномиальный коэффициент равен 0 (т.к. выборов такими параметрами просто не существует).

Далее, преобразуем немного наши индексы: Здесь мы воспользовались соотношением, верным для любых и : Далее, просто сдвинем индекс суммирования на единичку, чтобы всё получилось красиво:

Следовательно, мы заключаем, что Но именно это мы с вами и хотели доказать.