Комбинаторика на Питергоре

Пусть имеется способов выбрать граммов без использования гири в г и способов набрать граммов с использованием гири в г.

Добавив к каждому из способов первой группы гирю в г, мы получим суммарный вес граммов. Значит, (способов выбрать граммов без единицы может быть равно нулю, поэтому знак больше или равно).

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

Следовательно, (при нечётном появляется ещё один способ взять гири вне этого алгоритма, поэтому знак больше или равно).

Сложив полученные два неравенства, имеем требуемое.