Докажите, используя принцип математической индукции, что значение выражения 9^n - 8n - 1 делится на 16 при любом натуральном значении n.

1) Проверим справедливость утверждения при :

2) Предположим, что при утверждение справедливо, то есть:

3) Докажем, что при справедливо утверждение:

Доказательство. Преобразуем:

Первое слагаемое делится на 16 по предположению, сделанному на втором шаге.

Рассмотрим второе слагаемое . Первый множитель 8 делится на 8. Заметим, что второй множитель является четным, так как выражение при дает нечетные числа, тогда числа вида являются четными. Таким образом, второе слагаемое делится на .

Итак, оба слагаемых делятся на 16. Значит и вся сумма делится на 16. Доказано.