Метод математической индукции при доказательстве утверждений в дискретной математике можно применить следующим образом: 2

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

В дискретной математике и информатике многие классы объектов определяются индуктивно. 2 В таких определениях явно или неявно участвует некоторая функция, задающая «сложность» объекта, и индукция идёт по значениям этой функции. 2

Для доказательства свойства объектов индуктивно определённого класса метод математической индукции применяется так: 2

1. Базис индукции состоит в проверке требуемого свойства у объектов минимальной сложности. 2
2. Шаг индукции состоит в предположении справедливости доказываемого свойства у всех объектов класса, имеющих сложность <= k, и проверке того, что все объекты большей сложности (обычно, сложности k+1), получаемые из них с помощью используемых при определении класса операций, также обладают требуемым свойством. 2