Индукцией доказывают не только формулы сумм. Схема та же: база, предположение, шаг — меняется лишь то, как из случая n получить случай n + 1.
Делимость. Докажем, что 6ⁿ + 10n - 1 делится на 5. База: 6 + 10 - 1 = 15. Шаг: 6⁽n + 1) + 10(n + 1) - 1 = 6(6ⁿ + 10n - 1) - 50n + 15; первое слагаемое делится на 5 по предположению, а -50n + 15 = 5(3 - 10n) — тоже.
Множества. У множества из n элементов 2ⁿ подмножеств: добавив новый элемент, каждое старое подмножество можно взять с ним или без него — подмножеств становится вдвое больше.
Геометрия. n прямых общего положения делят плоскость на 1 + (n(n + 1))/2 частей: новая, (n + 1)-я прямая пересекает n старых в n точках, делится ими на n + 1 кусков, и каждый кусок разрезает одну часть плоскости надвое.
Размен. Любую сумму от 8 рублей можно набрать монетами по 3 и 5 рублей. База: 8 = 3 + 5. Шаг: если в наборе есть пятирублёвая монета, заменим её двумя трёхрублёвыми (+1 рубль); если нет, то трёхрублёвых не меньше трёх — заменим три из них двумя пятирублёвыми (9 → 10).
Шаг через несколько. Иногда удобнее переходить от n к n + 3 (или n + 2): тогда базу проверяют сразу для нескольких значений подряд. Например, квадрат можно разрезать на 6, 7 и 8 квадратов, а разрезав один из квадратов на четыре, получаем на 3 квадрата больше.