Шувалова Э.З., Агафонов Б.Г., Богатырев Г.И., Повторим математику. Издание второе, дополненное. Учебное пособие для поступающих в вузы. М., Высшая школа, 1974, с. 519
ВВЕДЕНИЕ
1. Доказательство от противного. Пусть А – условие теоремы, т.е. то, что предполагается данным, а В – её заключение, т.е. то, что требуется доказать. Тогда теорема схематически записывается в виде А → В и читается так, «из А следует В».
Метод доказательства от противного теоремы А – В состоит в следующем. Предполагается противное (противоречивое) искомому В положение В′. Если на основании сделанного предположения В′ и условия А удается получить некоторое неверное утверждение, то положение В′ не имеет места, то есть справедливо В и тем самым теорема А → В доказана.
2. Необходимость и достаточность. Пусть В – какое-либо положение, А – некоторое условие.
А называется необходимым условием для В, если из В вытекает А: В → А.
А называется достаточным условием для В, если из А следует В: А → В.
Всякую теорему можно сформулировать с помощью терминов «необходимо», «достаточно».
А называется необходимым и достаточным условием для В, если В → А и одновременно А → В.
Термин «необходимо и достаточно» можно заменить выражениями «если и только если», «тогда и только тогда».
Поясним понятия «необходимо» и «достаточно» на примерах.
Пример 1. Четность числа есть необходимый признак делимости на 4.
Здесь А –четность числа, В – его делимость на 4. Очевидно В → А. Однако из А не следует В (так чётное числ 6 не делится на 4). Поэтому чётность числа – необходимое, но не достаточное условие делимости на 4.
Пример 2. Достаточным условием делимости на 4 (положение В) является следующий признак: число оканчивается двумя нулями (условие А).
В самом деле, из условия А следует В (см. гл. 1, §1). Однако из В не следует А (так, число 24 делится на 4, но не оканчивается двумя нулями). Поэтому условие А только достаточное; необходимым для В оно не является.
Пример 3. Для делимости на 3 (В) необходимо и достаточно, чтобы сумма цифр числа делилась на 3 (А).
В самом деле, здесь справедливы два утверждения: если число делится на 3 (А), то и сумма цифр делится на 3 (А), т.е. В → А (необходимость), и обратно – если сумма цифр числа делится на 3 (А), то и само число делится на 3 (В), т.е. А → В (достаточность). Доказательство приведено в гл. 1, §1.
3. Метод математической индукции. Пусть некоторое утверждение зависит определённым образом от натурального числа n, которое принимает все значения, начиная от данного р (р – натуральное число или р = 0).
Принимаем следующий принцип. Если: а) утверждение верно для n = p и б) из справедливости этого утверждения для какого-нибудь натурального числа n = k вытекает справедливость его и для следующего числа n = k + 1, то утверждение справедливо для любого натурального n ≥ p.
На этом принципе основан метод математической индукции.
Чтобы доказать методом математической индукции, что некоторое утверждение верно для любого натурального n ≥ p надо: а) проверить утверждение для n = p и б) и допустив справедливость этого утверждения для n = k, доказать справедливостьего и для n = k + 1. Только при одновременном выполнении а) и б) заключаем, что утверждение верно для любого n ≥ p.
Часто наименьшим числом р, для которого верно утверждение, является число р = 1.