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

Доказательство с помощью метода математической индукции проводится в два этапа: 4

1. База индукции (базис индукции). 4 Проверяется истинность утверждения при n=1 (или любом другом подходящем значении n). 4
2. Индуктивный переход (шаг индукции). 4 Считая, что справедливо утверждение P(k) при n=k, проверяется истинность утверждения P(k+1) при n=k+1. 4