Математика и информатика. Филимонова Л.В - 7 стр.

                                            7

способ доказательства. Если требуется доказать истинность предло-
жения А(n) для всех натуральных n, то, во-первых, следует проверить
истинность высказывания А(1) и, во-вторых, предположив истинность
высказывания А(k), попытаться доказать, что высказывание А(k+1)
истинно. Если это удается доказать, причем доказательство остается
справедливым для каждого натурального значения k, то в соответст-
вии с принципом математической индукции предложение А(n) при-
знается истинным для всех значений n.
        Пример 1.4. Доказать истинность предложения
                        А(n) ≡ {число 5⋅23n – 2 + 33n – 1 кратно 19}, n ∈ N.
Решение: 1) Высказывание А(1) ≡ {число 5⋅2 + 32 кратно 19} истинно.
2) Предположим, что для некоторого значения n=k
   А(k) ≡ {число 5⋅23k – 2 + 33k – 1 кратно 19}истинно. Тогда, так как
5⋅23 (k+1) – 2 + 33 (k+1) – 1 = 8⋅5⋅23k – 2 + 27⋅33k – 1 = 8 (5⋅23k – 2 + 33k – 1) + 19⋅33k
–1
   , очевидно, что и А(k+1) истинно. Действительно, первое слагаемое
делится на 19 в силу предположения, что А(k) истинно; второе сла-
гаемое тоже делится на 19. Оба условия принципа математической
индукции выполнены, следовательно, предложение А(n) истинно при
всех значениях n. ♦
        Рассмотрим некоторое обобщение принципа математической
индукции.
        Пусть p – некоторое целое число.
        Предложение А(n), где n – целое, истинно для всех целых зна-
чений
n ≥ p, если выполнены следующие два условия:
        1. Предложение А(n) истинно для n = p.
        2. Из предположения, что А(n) истинно для n = k ( k – целое, k
             ≥ p), следует, что оно истинно для следующего значения n=k
             + 1.
        При p = 1 получается первоначальная формулировка.
        Пример 1.5. Доказать, что любую сумму денег, большую 7 ко-
пеек, можно разменять только трехкопеечными и пятикопеечными
монетами.
        Решение: Пусть сумма равна n копейкам. Если n=8, что утвер-
ждение верно. Пусть утверждение верно для n=k. Могут представить-
ся только два случая для размена суммы в k копеек:
        а) потребовались только трехкопеечные монеты,
        б) потребовалась хотя бы одна пятикопеечная монета.
        В случае а) удаляем три трехкопеечные монеты, добавляем две
пятикопеечные и тем самым размениваем сумму в k + 1 копеек. В
случае б) удаляем одну пятикопеечную монету, добавляем две трех-
копеечные монеты и тем самым размениваем сумму в k + 1 копеек.
Ч.т.д. ♦