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

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

Система натуральных чисел, которую обозначают через 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 ⁿ >7 n +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 ⁿ >7 n +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 ⁿ >7 n +3 для всех натуральных n ³6.

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

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

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

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

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

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

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

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

Покажем, что

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

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

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

Доказательство. При n =2 имеем (1+ x)²=1+2 x + x ². Так как x ²>0, то (1+ x)²>1+2 x. Утверждение справедливо. По индуктивному предположению, оно справедливо при 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. Доказать, что 11 n ²-14 n +3³0 при всех целых n.

Доказательство. Очевидно, что для всех неположительных целых n 11 n ²–14 n +3³0. Методом математической индукции докажем, что для всех натуральных n 11 n ²-14 n +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=11 k ²+22 k +11–14 k –14+3=

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

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

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

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