Математическая индукция

Математическая индукция – это метод доказательства утверждений, которые зависят от натурального числа $n$: формул для сумм, делимости, неравенств. Здесь мы увидим, откуда происходит название метода, почему он верен и как его применять.

На этой странице: Неполная индукция · Полная индукция · Принцип математической индукции · Примеры · Индукция от ${n=m}$ · Гипотеза и доказательство · Задачи

Неполная индукция

Метод исследования, при котором мы рассматриваем отдельные элементы множества и по ним находим свойства всего множества, называется индуктивным методом. Когда рассмотрены не все случаи, говорят, что применена неполная индукция.

Вот пример из истории математики. Французский математик XVII века Пьер Ферма рассмотрел числа

${2^{2^1}+1=5}$, ${2^{2^2}+1=17}$, ${2^{2^3}+1=257}$, ${2^{2^4}+1=65\,537}$

и заметил, что все они простые. Он предположил, что число ${2^{2^n}+1}$ простое при любом натуральном $n$. При ${n=5}$ получается ${2^{2^5}+1=4\,294\,967\,297}$, и Ферма не смог проверить, есть ли у него нетривиальные делители. Позднее Эйлер показал, что оно делится на 641: ${4\,294\,967\,297}={641\cdot 6\,700\,417}$. Значит, предположение Ферма неверно.

Есть и примеры, в которых первый случай, опровергающий гипотезу, полученную неполной индукцией, лежит так далеко, что его невозможно достичь проверками. Например, кажется, что число ${991n^2+1}$ никогда не бывает точным квадратом. Это действительно так для любого натурального $n$, меньшего

${n}={12\,055\,735\,790\,331}\allowbreak{\,359\,447\,442\,538\,767}$,

но при этом 29-значном числе ${991n^2+1}$ уже является точным квадратом. Столько проверок не под силу даже самым быстрым компьютерам.

Эти примеры показывают, что вывод, основанный на неполной индукции, может оказаться неверным, поэтому неполной индукцией нужно пользоваться осторожно. Она полезна тем, что частные случаи подсказывают закономерность и помогают высказать гипотезу. Однако верность гипотезы нужно доказать другим способом.

Полная индукция

Если частных случаев конечное число и все они рассмотрены, вывод обоснован. Например, чтобы узнать, сколько простых чисел среди чисел от 1 до 10, достаточно проверить каждое из них: простые – 2, 3, 5 и 7. Вывод «в первом десятке 4 простых числа» не требует другого обоснования.

Метод, при котором мы исследуем все элементы множества и делаем вывод обо всём множестве, называется полной индукцией. Вывод, полученный полной индукцией, вполне достоверен, поэтому она является методом строгого доказательства.

Однако полная индукция применяется редко: она громоздка, когда случаев много, и неприменима, когда их бесконечно много. Бесконечное множество можно исследовать с её помощью, только если разбить его на конечное число частей и рассмотреть каждую из них отдельно.

Пример. Докажите, что квадрат натурального числа не может оканчиваться цифрой 2.

Последняя цифра квадрата зависит только от последней цифры числа. Поэтому разобьём натуральные числа на 10 частей по последней цифре и проверим каждую часть:

$n$ оканчивается на	0	1	2	3	4
$n^2$ оканчивается на	0	1	4	9	6
$n$ оканчивается на	5	6	7	8	9
$n^2$ оканчивается на	5	6	9	4	1

В строках для $n^2$ нет цифры 2, и задача решена.

Принцип математической индукции

Когда множество случаев бесконечно и его нельзя разбить на конечное число частей, применяют другие методы. Один из них – метод математической индукции. Он основан на одной из аксиом натуральных чисел, сформулированных итальянским математиком Джузеппе Пеано (1889 г.). Поэтому, несмотря на название, математическая индукция – дедуктивный метод.

Аксиома индукции. Если множество $M$ натуральных чисел содержит число 1 и вместе с каждым числом $k$ содержит и следующее число ${k+1}$, то $M$ содержит все натуральные числа.

В доказательствах она используется в следующем виде.

Принцип математической индукции. Пусть $T(n)$ – утверждение о натуральном числе $n$. Если $T(1)$ верно и для любого натурального $k$ из верности $T(k)$ следует верность ${T(k+1)}$, то $T(n)$ верно для любого натурального $n$.

Действительно, пусть $M$ – множество натуральных чисел, для которых $T(n)$ верно. По условию ${1\in M}$, и если ${k\in M}$, то ${k+1\in M}$. По аксиоме индукции $M$ содержит все натуральные числа, т.е. $T(n)$ верно для любого натурального $n$.

Поэтому доказательство по индукции состоит из трёх этапов:

База: проверяем, что утверждение верно при ${n=1}$.
Шаг индукции: предполагаем, что оно верно при некотором ${n=k}$ (индукционное предположение), и доказываем, что оно верно и при ${n=k+1}$.
Вывод: по принципу математической индукции утверждение верно для любого натурального $n$. Оно верно при ${n=1}$, следовательно, и при ${n=2}$, тогда и при ${n=3}$ и т.д.

Нужны и база, и шаг. Пусть $T(n)$ – утверждение «число ${n^2+n}$ нечётное». Шаг верен: если ${k^2+k}$ нечётно, то и ${(k+1)^2+(k+1)}={(k^2+k)+2(k+1)}$ нечётно. Однако база неверна (${1^2+1=2}$), и на самом деле ${n^2+n=n(n+1)}$ чётно при любом $n$.

Примеры

Пример 1. Докажите, что

${S_n}={1\cdot 2\cdot 3+2\cdot 3\cdot 4+\dots}+{n(n+1)(n+2)}={\frac{n(n+1)(n+2)(n+3)}{4}}$.

База. При ${n=1}$ левая часть равна ${S_1=1\cdot 2\cdot 3=6}$, а правая – ${\frac{1\cdot 2\cdot 3\cdot 4}{4}=6}$.

Шаг. Предположим, что формула верна при ${n=k}$, т.е. ${S_k}={\frac{k(k+1)(k+2)(k+3)}{4}}$. Тогда

${S_{k+1}}={S_k}+{(k+1)(k+2)(k+3)}={\frac{k(k+1)(k+2)(k+3)}{4}}+{(k+1)(k+2)(k+3)}={\frac{(k+1)(k+2)(k+3)(k+4)}{4}}$,

так как ${\frac{k}{4}+1=\frac{k+4}{4}}$. Это и есть формула при ${n=k+1}$.

Вывод. Формула верна при ${n=1}$, и из её верности при ${n=k}$ следует верность при ${n=k+1}$. По принципу математической индукции она верна для любого натурального $n$.

Пример 2. Докажите, что при любом натуральном $n$ число ${11^{n+2}+12^{2n+1}}$ делится на 133.

База. При ${n=1}$: ${11^3+12^3}={1331+1728}={3059}={133\cdot 23}$.

Шаг. Пусть ${11^{k+2}+12^{2k+1}=133p}$, где $p$ – целое число. Так как ${144=11+133}$,

${11^{k+3}+12^{2k+3}}={11\cdot 11^{k+2}}+{144\cdot 12^{2k+1}}={11\left(11^{k+2}+12^{2k+1}\right)}+{133\cdot 12^{2k+1}}={133\left(11p+12^{2k+1}\right)}$.

Вывод. Выражение делится на 133 при ${n=1}$, и если оно делится при ${n=k}$, то делится и при ${n=k+1}$. Следовательно, оно делится на 133 при любом натуральном $n$.

Пример 3. Докажите, что множество ${M_n=\{a_1,a_2,\dots,a_n\}}$ имеет $2^n$ подмножеств.

База. При ${n=1}$ множество ${M_1=\{a_1\}}$ имеет два подмножества: пустое множество и само $M_1$. Их число равно ${2^1}$.

Шаг. Предположим, что ${M_k=\{a_1,\dots,a_k\}}$ имеет $2^k$ подмножеств, и рассмотрим ${M_{k+1}}={\{a_1,\dots,a_k,a_{k+1}\}}$. Подмножества $M_{k+1}$, не содержащие $a_{k+1}$, – это в точности подмножества $M_k$, т.е. их $2^k$. Подмножества, содержащие $a_{k+1}$, получаются добавлением $a_{k+1}$ к каждому подмножеству $M_k$, поэтому их тоже $2^k$. Всего ${2^k+2^k=2\cdot 2^k=2^{k+1}}$.

Вывод. По принципу математической индукции $M_n$ имеет $2^n$ подмножеств при любом натуральном $n$.

Индукция, начинающаяся с ${n=m}$

В приложениях часто используется и следующая формулировка принципа.

Пусть $m$ – натуральное число. Если утверждение $T(m)$ верно и для любого ${k\ge m}$ из верности $T(k)$ следует верность ${T(k+1)}$, то $T(n)$ верно для любого натурального ${n\ge m}$.

Здесь база – это проверка утверждения при ${n=m}$.

Пример 4. Докажите, что ${2^n\gt 2n+1}$ для любого натурального ${n\ge 3}$.

База. При ${n=3}$: ${2^3=8\gt 7=2\cdot 3+1}$. (При ${n=2}$ неравенство неверно: ${2^2=4\lt 5}$.)

Шаг. Пусть ${2^k\gt 2k+1}$ при некотором ${k\ge 3}$. Докажем, что ${2^{k+1}\gt 2(k+1)+1}$. Кроме индукционного предположения используем и ${2^k\gt 2}$:

${2^{k+1}}={2^k+2^k}\gt{(2k+1)+2}={2(k+1)+1}$.

Вывод. По принципу математической индукции (последняя формулировка) ${2^n\gt 2n+1}$ для любого натурального ${n\ge 3}$.

Гипотеза и доказательство

В исследованиях часто сначала нужно найти закономерность, высказать о ней утверждение и только потом доказать его для любого натурального $n$. Тогда последовательно применяют неполную индукцию, чтобы получить гипотезу из частных случаев, и математическую индукцию, чтобы её доказать. Этапов три:

опыт и наблюдение;
выдвижение гипотезы;
доказательство гипотезы.

Пример 5. Найдите сумму первых $n$ нечётных чисел.

Задача означает, что нужно найти формулу для суммы ${S_n}={1+3+5+\dots}+{(2n-1)}$, более короткую, чем непосредственное сложение.

Первый этап. Вычисляем $S_n$ для нескольких последовательных значений $n$: ${S_1=1}$, ${S_2=1+3=4}$, ${S_3=1+3+5=9}$, ${S_4=1+3+5+7=16}$ и т.д.:

$n$	1	2	3	4	5	6
$S_n$	1	4	9	16	25	36

Ищем правило, по которому каждое число второй строки получается из числа над ним. Замечаем, что ${S_1=1^2}$, ${S_2=2^2}$, ${S_3=3^2}$, ${S_4=4^2}$, ${S_5=5^2}$ и ${S_6=6^2}$.

Второй этап. Правило верно при ${n=1,2,\dots,6}$, и естественно предположить, что оно верно при любом $n$:

${1+3+5+\dots}+{(2n-1)}={n^2}$.

Найти такую гипотезу помогает умение наблюдать, строить догадки и проверять их, опыт решения похожих задач и аналогии с уже известными задачами.

Третий этап. Доказываем гипотезу методом математической индукции. При ${n=1}$ она верна: ${S_1=1=1^2}$. Пусть ${S_k=k^2}$. Тогда

${S_{k+1}}={S_k+(2k+1)}={k^2+2k+1}={(k+1)^2}$.

По принципу математической индукции ${S_n=n^2}$ при любом натуральном $n$, т.е. гипотеза верна.

Здесь мы намеренно разделили решение на три этапа, чтобы был хорошо виден его ход. На практике этапы естественно переходят один в другой.

Задачи

В задачах 1–6 докажите, что утверждение верно для любого натурального $n$.

1. ${\frac{1}{1\cdot 3}+\frac{1}{3\cdot 5}+\frac{1}{5\cdot 7}+\dots}+{\frac{1}{(2n-1)(2n+1)}}={\frac{n}{2n+1}}$

База: ${\frac{1}{1\cdot 3}=\frac{1}{3}=\frac{1}{2\cdot 1+1}}$.

Шаг: ${\frac{k}{2k+1}}+{\frac{1}{(2k+1)(2k+3)}}={\frac{2k^2+3k+1}{(2k+1)(2k+3)}}={\frac{(2k+1)(k+1)}{(2k+1)(2k+3)}}={\frac{k+1}{2k+3}}$.

2. ${\frac{1}{1\cdot 4}+\frac{1}{4\cdot 7}+\frac{1}{7\cdot 10}}+{\dots+\frac{1}{(3n-2)(3n+1)}}={\frac{n}{3n+1}}$

База: ${\frac{1}{1\cdot 4}=\frac{1}{4}=\frac{1}{3\cdot 1+1}}$.

Шаг: ${\frac{k}{3k+1}}+{\frac{1}{(3k+1)(3k+4)}}={\frac{3k^2+4k+1}{(3k+1)(3k+4)}}={\frac{(3k+1)(k+1)}{(3k+1)(3k+4)}}={\frac{k+1}{3k+4}}$.

3. ${\frac{1}{a(a+1)}}+{\frac{1}{(a+1)(a+2)}}+{\dots+\frac{1}{(a+n-1)(a+n)}}={\frac{n}{a(a+n)}}$, где ${a\gt 0}$

База: при ${n=1}$ обе части равны ${\frac{1}{a(a+1)}}$.

Шаг: ${\frac{k}{a(a+k)}}+{\frac{1}{(a+k)(a+k+1)}}={\frac{k(a+k+1)+a}{a(a+k)(a+k+1)}}={\frac{(a+k)(k+1)}{a(a+k)(a+k+1)}}={\frac{k+1}{a(a+k+1)}}$, так как ${ka+k^2+k+a}={(a+k)(k+1)}$.

4. ${2^{3n}-7n-1}$ делится на 49

${2^{3n}=8^n}$. База: ${8-7-1=0}$ делится на 49.

Шаг: ${8^{k+1}-7(k+1)-1}={8\left(8^k-7k-1\right)+49k}$. Оба слагаемых делятся на 49.

5. ${2^{2n}+15n-1}$ делится на 9

${2^{2n}=4^n}$. База: ${4+15-1=18=9\cdot 2}$.

Шаг: ${4^{k+1}+15(k+1)-1}={4\left(4^k+15k-1\right)}-{9(5k-2)}$. Оба члена делятся на 9.

6. ${2^{n+2}\cdot 3^n+5n-4}$ делится на 25

Пусть ${A_n=2^{n+2}\cdot 3^n+5n-4}$. База: ${A_1=8\cdot 3+5-4=25}$.

Шаг: ${A_{k+1}}={6\cdot 2^{k+2}\cdot 3^k+5k+1}={6A_k-25(k-1)}$, а $6A_k$ и ${25(k-1)}$ делятся на 25.

В задачах 7–10 найдите сумму. Вычислите её для нескольких значений $n$, выскажите гипотезу и докажите её по индукции.

7. ${1+2+3+\dots+n}$

${\frac{n(n+1)}{2}}$. Шаг: ${\frac{k(k+1)}{2}+(k+1)}={\frac{(k+1)(k+2)}{2}}$.

8. ${2+4+6+\dots+2n}$

${n(n+1)}$. Шаг: ${k(k+1)+2(k+1)}={(k+1)(k+2)}$.

9. ${1\cdot 2+2\cdot 3+3\cdot 4}+{\dots+n(n+1)}$

${\frac{n(n+1)(n+2)}{3}}$. Шаг: ${\frac{k(k+1)(k+2)}{3}}+{(k+1)(k+2)}={\frac{(k+1)(k+2)(k+3)}{3}}$.

10. ${\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}}+{\dots+\frac{1}{n(n+1)}}$

Суммы равны ${\frac{1}{2}}$, ${\frac{2}{3}}$, ${\frac{3}{4}}$, …, поэтому гипотеза – ${\frac{n}{n+1}}$. Шаг: ${\frac{k}{k+1}+\frac{1}{(k+1)(k+2)}}={\frac{k^2+2k+1}{(k+1)(k+2)}}={\frac{k+1}{k+2}}$.