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

Система натуральных чисел

Система натуральных чисел, которую обозначают через N, есть определенное фиксированное множество, элементы которого 1, 2, 3, ... называютсянатуральными числами. Множество N обладает следующими свойствами:

1. В N определена бинарная алгебраическая операция сложения, которая:

a) коммутативна, т. е. a+b=b+a "a, bÎN;

b) ассоциативна, т. е. (a+b)+c=a+(b+c) "a, b, cÎN.

2. В N определена бинарная алгебраическая операция умножения, которая:

a) коммутативна, т. е. a×b=b×a "a, bÎN;

b) ассоциативна, т. е. (a×b)×c=a×(b×c) "a, b, cÎN.

3. Сложение и умножение связаны законом дистрибутивности

(a+b)×c=a×c+b×c "a, b, cÎN.

4. В N определено отношение сравнения чисел по величине “a меньше b” (a<b), при этом выполняются свойства:

a) для любых a,bÎN выполняется одно из соотношений a<b, b<a, a=b (свойство линейности);

b) соотношение a<b имеет место тогда и только тогда, когда существует такое xÎN, что a+x=b (свойство положительности);

c) в любом непустом множестве MÍN найдется минимальное число, т. е. такое натуральное число aÎM, что a£x имеет место для всех xÎM (свойство минимальности);

d) минимальный элемент множества N, обозначаемый через 1, таков, что для всякого aÎN имеет место 1×a=a (существование единичного элемента).

Систему N часто называют натуральным рядом.

Замечание. Если a<b, то говорят: “a меньше b”, а также “b больше a”, “a предшествует b”, “b следует за a”. Обозначение b>a есть другое обозначение для a<b. Соотношение a£b означает, что a<b или a=b; b³a есть другое обозначение для a£b.

Из основных свойств сложения и умножения вытекают следующие свойства.

Свойство сокращения сложения

Если a+x=a+y, то x=y.

Действительно, допустим, что x¹y, тогда, по свойству линейности, или x<y, или y<x. Пусть x<y, тогда существует zÎN такое, что x+z=y, следовательно, a+x=a+y=a+(x+z)=(a+x)+z. Из того, что a+y=(a+x)+z, следует, что a+x<a+y, чего быть не может. Аналогично получим противоречие, если полагать, что y<x.

Свойство сокращения умножения

Если a×x=a×y, то x=y.

Действительно, допустим, что x¹y. Не нарушая общности рассуждения, можно полагать, что x<y, тогда x+z=y, а потому a×x=a×y=a(x+z)=ax+az. Из того что ay=ax+az, следует, что ax<ay вопреки тому, что ax=ay. Предположение о том, что x¹y, неверно.

Свойство транзитивности

Если a<b и b<c, то a<c.

Из условия следует, что b=a+z и c=b+u, тогда c=b+u=(a+z)+u=a+(z+u)= a+v. Отсюда следует, что a<c.

Стабильность сложения

Для всех a,b,cÎN, если a<b, то a+c<b+c.

Действительно, если a<b, то b=a+x. Но тогда

b+c=(a+x)+c=a+(x+c)=(a+c)+x.

Отсюда a+c<b+c.

Стабильность умножения

Для всех a, b, cÎN если a<b, то ac<bc. Действительно, если a<b, то b=a+x. Но тогда bc=(a+x)c=ac+cx. Отсюда ac<bc.

6. Еслиa¹1,то ab>b, a, bÎN.

Так как a¹1,то a>1, тогда ab>1×b.

Свойство Архимеда

Для любых a, bÎN существует nÎN такое, что n×a>b.

Действительно, в качестве n можно взять любое натуральное число, большее b. Пусть n=b+1. Так как a³1, то na=(b+1)a>b, т. е. na>b.

Значение. В свойствах 3, 4, 5 вместо < можно взять £ .

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

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

Поскольку в методической литературе часто встречаются такие понятия, как полная индукция, неполная индукция и метод математической индукции, то начнем с их определения.

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

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

Например, известно, что имеется пять типов правильных многогранников.

1. Тетраэдр. В каждой вершине сходятся 3 ребра. Имеет 4 грани (треугольные), 6 ребер, 4 вершины. Тетраэдр является правильной треугольной пирамидой (рис. 1).

Рис. 1

2. Куб. В каждой вершине сходятся 3 ребра. Имеет 6 граней (квадратные), 12 ребер, 8 вершин (рис.2).

Рис. 2

3. Октаэдр. В каждой вершине сходятся 4 ребра. Имеет 8 граней (треугольных), 12 ребер, 6 вершин (рис. 3).

Рис. 3

4. Икосаэдр. В каждой вершине сходятся 5 ребер. Имеет 20 граней (треугольных), 30 ребер, 12 вершин (рис. 4).

Рис. 4

5. Додекаэдр. В каждой вершине сходятся 3 ребра. Имеет 12 граней (пятиугольных), 30 ребер, 20 вершин (рис. 5).

Рис. 5

Обозначим через Г - число граней, Р - число ребер, В - число вершин. Имеет место утверждение: "Для пяти типов правильных многоугольников имеет место соотношение Г+В=Р+2".

Тетраэдр Куб Октаэдр Икосаэдр Додекаэдр

4 + 4 = 6 + 2 6 + 8 =12 + 2 8 + 6 = 12 + 2 20 + 12 = 30 + 2 20 + 12 = 30 + 2

Утверждение доказано полной индукцией.

Пример. Доказать, что любое четное натуральное число 4£n£16 представимо в виде суммы двух простых чисел. Действительно,

4=2+2, 6=3+3, 8=3+5, 10=5+5, 12=5+7, 14=7+7, 16=5+11.

Тем самым утверждение доказано.

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

Иногда общий результат удается предугадать после рассмотрения не всех, а достаточно большого числа частных случаев (так называемая неполная индукция).

Результат, полученный неполной индукцией, может быть как истинным, так и ложным. В самом деле, рассмотрим многочлен f(n)=n²+n+41. Легко видеть, что f(0)=41, f(1)=43, f(2)=47, f(3)=53, f(4)=61. Числа 41, 43, 47, 53, 61 - простые. Напрашивается предположение, что f(n) для всех неотрицательных n – простое число. Однако при n=41 очевидно, что – составное.

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

Рассмотрим следующую задачу.

При каких натуральных n справедливо неравенство 2ⁿ>7n+3?

При	n=1	2>10	ложно
При	n=2	4>17	ложно
При	n=3	8>24	ложно
При	n=4	16>31	ложно
При	n=5	32>38	ложно
При	n=6	64>45	истинно
При	n=7	128>52	истинно

На основании неполной индукции можно предполагать, что 2ⁿ>7n+3 для всех натуральных чисел n³6. Эту гипотезу мы докажем позже. А пока еще раз отметим, что неполная индукция в математике не считается законным методом строгого доказательства. Она является средством выдвижения гипотез, справедливость которых, как правило, доказывают методом математической индукции.

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

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

Пусть дано некоторое утверждение, зависящее от натурального n. Обозначим его через A(n). Если данное утверждение справедливо при n=1, т. е. A(1) истинно и из его истинности при n=k следует его истинность при n=k+1, то A(n) истинно при всех натуральных n.

Действительно, пусть A(1) истинно и из истинности A(k) следует истинность A(k+1). Тогда можно рассуждать так: истинность утверждения проверена при n=1, но по допущению утверждение верно и при n=1+1=2, а потому оно верно и при n=2+1=3 и так далее, т. е. справедливо при всех значениях n. Мы здесь уверены, что каждый раз сможем сделать следующий шаг, и поэтому очевидно, что утверждение справедливо для любого n, так как до любого натурального числа n можно добраться конечным числом шагов, начиная с n=1.

Таким образом, чтобы доказать справедливость некоторого утверждения при любом натуральном n, надо доказать два факта:

1) справедливость при n=1;

2) всякий раз из его справедливости при n=k следует его справедливость при n = k+1.

В этом и состоит принцип математической индукции: доказываем, что утверждение справедливо при n=1 (базис индукции), затем предполагаем, что утверждение справедливо при n=k (индуктивное предположение), доказываем его справедливость при n=k+1.

В ряде случаев бывает нужно доказать справедливость некоторого утверждения не для всех натуральных n, a лишь для n³p, где р - некоторое натуральное число. В этом случае принцип математической индукции формулируется следующим образом.

Если предложение A(n) истинно при n=p и если A(k)ÞA(k+1) для любого натурального k³p, то оно справедливо при любом натуральном n³p.

Теперь рассмотрим некоторые задачи.

Задача 1.Доказать, что n-й член арифметической прогрессии выражается формулой a_n=a₁+d(n-1).

По определению арифметической прогрессии,

Гипотезу

a_n= a₁+ d(n-1)

докажем методом математической индукции. При n=1 имеем a₁=a₁+d(1-1)= =a₁, гипотеза верна. По индуктивному предположению, гипотеза верна при n=k, т. е. a_k=a₁+d(n-1). Докажем ее справедливость при n=k+1, т. е. покажем, что a_k₊₁=a₁+dk.

В самом деле, по определению арифметической прогрессии, a_k₊₁=a_k+d. Учитывая индуктивное предположение, получаем:

a_k₊₁=a_k+d=a₁+d(k-1)+d=a₁+kd-d+d=a₁+dk.

На основании принципа математической индукции заключаем, что гипотеза верна при всех nÎN, тем самым имеем a_n=a₁+d(n-1).

Задача 2. Доказать, что 2ⁿ>7n+3 для всех натуральных n³6.

Доказательство. При n=6 имеем 2⁶>45, т. е. утверждение справедливо. По индуктивному предположению, утверждение справедливо при n=k:

2^k>7k+3 (k³6).

Докажем справедливость утверждения при n=k+1, т. е. покажем, что

2^k⁺¹>7(k+1)+3=7k+10. (1)

По индуктивному предположению, имеем

2^k >7k+3. (2)

Умножая обе части (2) на 2, получим

2^k⁺¹ >14k+6. (3)

Покажем, что

14k+6>7k+10. (4)

Оценим разность 14k+6-(7k+10)=14k+6-7k-10=7k-4; т. к. k³6, то 7k-4>0, следовательно, (4) доказано. Из (1) и (3) следует, что 2^k⁺¹>7k+10. На основании принципа математической индукции утверждение справедливо при любом натуральном n³6, то есть 2ⁿ>7n+3 для всех натуральных n³6.

Задача 3. Доказать, что для всех натуральных n³2 (1+x)ⁿ>1+nx, где x>-1, x¹0 (неравенство Бернулли).

Доказательство. При n=2 имеем (1+x)²=1+2x+x². Так как x²>0, то (1+x)²>1+2x. Утверждение справедливо. По индуктивному предположению, оно справедливо при n=k, т. е.

(1+x)^k>1+kx. (5)

Докажем, что оно справедливо при n=k+1, т. е.

(1+x)^k⁺¹>1+(k+1)x. (6)

В самом деле, умножая обе части неравенства (5) на положительную величину 1+x, получим

т. е. (1+x)^k⁺¹>1+(k+1)x. Неравенство (6) доказано. На основании принципа математической индукции заключаем, что (1+x)ⁿ>1+nx для всех n³2.

Задача 4.Доказать, что для всех натуральных n>1 имеет место неравенство

. (7)

Доказательство. При n=2 имеем

Утверждение справедливо. По индуктивному предположению, оно справедливо при n=k, т. е.

. (8)

Докажем его справедливость при n=k+1, т. е. покажем, что

. (9)

Действительно,

(10)

В (10) выражение, стоящее в первых скобках, по индуктивному предположению, больше 13/24. Покажем, что

Действительно,

Тем самым справедливость неравенства (9) установлена, а потому на основании принципа математической индукции неравенство (7) справедливо для всех натуральных n>1.

Задача 5.Доказать, что 11n²-14n+3³0 при всех целых n.

Доказательство.Очевидно, что для всех неположительных целых n 11n²–14n+3³0. Методом математической индукции докажем, что для всех натуральных n 11n²-14n+3³0.

При n=1 имеем 11-14+3=14–14=0. Утверждение справедливо. По индуктивному предположению оно справедливо при n=k, т. е.

11 ²-14 +3³0. (11)

Покажем его справедливость при n=k+1, то есть докажем, что

11(k+1)²–14(k+1)+3³0 (12)

В самом деле,

11(k+1)²–14(k+1)+3=11k²+22k+11–14k–14+3=

=(11k²–14k+3)+(22k–3).

Теперь справедливость неравенства (12) вытекает из того, что 22k–3>0 для всех натуральных k и неравенства (11). Тем самым, согласно принципу математической индукции, данное утверждение справедливо при любых натуральных n. Итак, 11n²-14n+3³0 для всех целых n.

Задача 6.Найти все целые решения неравенства 2x+1<2log₂(x+3).

Решение. Данное неравенство имеет смысл лишь при x>-3. Непосредственная проверка показывает, что числа -2, -1, 0, 1 являются решениями указанного неравенства. При x=2 имеем 5<2log₂5 или log₂5²<log₂25. Очевидно, что это ложно. Есть предположение, что 2x+1>2log₂(x+3) для всех натуральных x³2. Для удобства неравество 2x+1>2log₂(x+3) перепишем так:

2²^x⁺¹>(x+3)² (13)

и покажем, что для всех x³2 оно справедливо.

При x=2 имеем 2⁵>5² - истинно. По индуктивному предположению, оно справедливо при x=k

. (14)

Покажем, что оно имеет место и при x=k+1, т. е.

. (15)

Умножая обе части (14) на 2², получим

. (16)

Покажем, что

. (17)

Оценим разность

тем самым справедливость неравенства (17), а следовательно, и (15) установлена. Согласно принципу математической индукции неравенство (13) имеет место для всех натуральных x³2. Следовательно, целыми решениями неравенства являются числа -2, -1, 0, 1.

Задача 7.Доказать, что при любом натуральном n справедливо тождество:

(18)

Доказательство. При n=1 имеем 1×2=2. C другой стороны,

т. е. 2=2. Утверждение справедливо. По индуктивному предположению, оно справедливо при n=k, т. е.

. (19)

Докажем, что оно справедливо при n=k+1, т. е. покажем, что

. (20)

В самом деле,

Справедливость (20) установлена. Согласно принципу математической индукции, тождество (18) верно при любом натуральном n.

Задача 8.Доказать, что при любом неотрицательном целом n

Доказательство. При n=0 имеем , и, следовательно, сформулированное утверждение справедливо. По индуктивному предположению имеем (7^k⁺²+8²^k⁺¹) 57. Докажем справедливость утверждения при n=k+1, т. е. покажем, что

(7^k⁺³+8²^k⁺³) 57

В самом деле,

(7^k⁺²+8²^k⁺¹) 57 по индуктивному предположению. Следовательно,

Тем самым при любом неотрицательном целом n.

Задача 9.Доказать, что число диагоналей выпуклого n-угольника (n³3) равно

Доказательство. Число диагоналей обозначим через D_n. В этих обозначениях мы должны показать, что D_n=n(n-3)/2. При n=3 имеем D₃=3(3-3)/2, т. е. число диагоналей треугольника равно нулю; тем самым утверждение истинно. По индуктивному предположению, при n=k имеем D_k=k(k-3)/2. Покажем, что при n=k+1 D_k₊₁=(k+1)(k-2)/2. Пусть A₁A₂…A_k A_k₊₁ - выпуклый (k+1)-угольник. Соединив А₁ с А_k получим выпуклый k-угольник, у которого, по индуктивному предположению, k(k-3)/2 диагоналей. Остается подсчитать, сколько диагоналей у (k+1)-угольника, исходящих из вершины А_k₊₁, плюс еще диагональ А₁А_k. Очевидно, что из вершины A_k₊₁исходят k-2 диагонали. Учитывая и А₁А_k, получим, что к D_k следует прибавить (k-2)+1= k-1 диагоналей. Таким образом, у выпуклого (k+1)-угольника число диагоналей равно D_k+k-1, т. е.

Тем самым, согласно принципу математической индукции, D_n=n(n-3)/2 для всех натуральных n³3.

Задача 10. Доказать, что сумма внутренних углов выпуклого n-угольника (n³3) равна 180⁰×(n-2).

Доказательство. Обозначим сумму внутренних углов выпуклого n-угольника через S_n. При n=3 имеем

S₃=180⁰×(3-2)=180⁰,

т. е. утверждение верно. По индуктивному предположению, утверждение справедливо при n=k, т. е. S_k=180⁰(k-2). Покажем, что оно справедливо и при n=k+1, т. е. S_k₊₁=180⁰(k-1). Пусть A₁A₂…A_kA_k₊₁ выпуклый (k+1)-угольник. Соединим А₁ с А_k. Имеем A₁A₂ …A_k - выпуклый k-угольник, у которого, по индуктивному предположению, S_k=180⁰(k-2). Очевидно, что

а поэтому утверждение справедливо для любого выпуклого n-угольника.

Задача 11. Доказать, что число подмножеств n-элементного множества равно 2ⁿ.

Доказательство. Обозначим через S(n) число подмножеств n-элементного множества. При n=1 имеем S(1)=2, т. е. одноэлементное множество имеет два подмножества: Øи{a}. Утверждение справедливо. По индуктивному предположению, оно справедливо при n=k, т. е. k-элементное множество имеет 2^k подмножеств:

Покажем его справедливость при n=k+1, т. е. покажем, что (k+1)-элементное множество имеет 2^k⁺¹ подмножеств. В самом деле, пусть A={a₁, a₂, …, a_k, a_k₊₁}. Данное (k+1)-элементное множество получается из k-элементного множества B={a₁, a₂, …, a_k} добавлением элемента a_k₊₁. Любое подмножество множества A или содержит a_k₊₁ или не содержит. Подмножества, не содержащие элемента a_k₊₁, являются подмножествами B; их число, по индуктивному предположению, равно 2^k. Отбрасывая элемент a_k₊₁ из подмножеств A, мы получим все подмножества множества B. Таким образом, число подмножеств A равно 2^k+2^k, т. е. S(k+1)=2^k+2^k=2^k⁺¹. Согласно принципу математической индукции, утверждение верно при всех натуральных n.