Спирина, М.С. Дискретная математика

Методом математической индукции можно доказывать нера­ венства. При этом нужно особенно внимательно относиться к пер­ вому этапу алгоритма, так как в условии не всегда оговаривается его область определения. Задача 30, Доказать справедливость неравенства 2я > 2я + 1. Решение. Проверим неравенство для п = 1. Имеем 2 > 3 ложно, для п = 2 имеем 22> 5 ложно, для п = 3 имеем 23> 7 истинно. Таким образом, неравенство может быть верным для всех п > 3, л е N. Гипотеза: неравенство справедливо Ук > 3, т.е. 2* > 2 к+ 1. Докажем справедливость формулы для п = к + 1, т. е. 2к + 1> 2 (к + + 1) + 1 или 2к + 1> 2к + 3. Действительно, 2к + 1= 2 ■ 2к > 2(2 к + 1) согласно гипотезе. Тогда имеем 2(2 к + 1) = (2 к + 1) + (2 к + 1) = (2 к + 1 + 2) + (2 к + 1 - 2) = = (2 к + 3) + ( 2к - 1) > 2к + 3. Следовательно, 2к + 1> 2к + 3, поэтому можно утверждать справедливость неравенства 2я> 2п + 1для Уп > 3, п е N, что и требовалось доказать. ? Дает ли метод математической индукции вывод индуктивного харак­ тера? Почему метод носит такое название? Метод математической индукции применяется также и для доказательства теорем. Докажем методом математической индук­ ции знаменитую теорему Эйлера о соотношении вершин, ребер и областей плоского графа (см. гл. 2). Теорема Эйлера. Пусть G — связный планарный граф, у кото­ рого п вершин, т ребер, а его плоская реализация разбивает плос­ кость на г областей. Тогда справедливо соотношение и - т + г= 2. Доказательство. Проведем индукцию по т. База т = 0. Тогда граф имеет одну вершину я = 1 и не разбивает плоскость на области, т.е. r= 1. Подставив значения т, п и г в формулу Эйлера, имеем верное равенство 1 - 0 + 1 = 2 = > 2 = 2. Пусть теорема верна для всех графов, имеющих т - к ребер, и формула я - к + г = 2 истинна. Докажем справедливость для т = к + 1 ребра. Для этого добавим графу еще одно ребро, при этом возможны два варианта. Если новое ребро инцидентно лишь имеющимся в графе реб­ рам, то новых вершин не добавилось, значит, я ' = я. Новое ребро разбило одну из существующих областей на две части, т.е. г' = г + 1. Поэтому формула Эйлера имеет вид я ' - т' + г' = 2 или п - (к + 1) + + (г + 1) = 2, что эквивалентно п - к + г = 2, а это истинно по нашему допущению. Если новое ребро соединяет существующие вершины с новой, то я ' = я + 1, но новых областей не добавилось г' = г. Подставим эти значения в формулу Эйлера и получим я + 1 - ( & + 1) + г = 2 , т.е. я - к + г = 2, что подтверждает справедливость теоремы. МММ также дает возможность изучать свойства конечных мно­ жеств. 274