Rambler's Top100





4
ВВОДНАЯ ГЛАВА
МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ (ММИ)
§1. Формулировки ММИ. Доказательство равенств
Дискретная математика это цикл математических наук, изу-
чающих свойства конечных множеств. В настоящее время эти науки
бурно развиваются, что определяется тремя очень важными факторами:
1) развитием компьютерной техники и компьютерных наук, кото-
рые базируются, а по существу являются продолжением дискретной
математики;
2) запросами различных прикладных наук теории управления,
экономики, оптимизации и многих, многих других;
3) логикой внутреннего развития этих наук: появлением новых раз-
делов, глубоких интересных проблем, развитием мощных методов их
решения.
Все это и предопределило тот факт, что различные разделы дис-
кретной математики все настойчивее внедряются не только в универси-
теты, но и в технические и экономические и даже в гуманитарные вузы.
ММИ лежит в основе доказательства огромного числа теорем в
различных разделах дискретной математики. Подчеркивая это обстоя-
тельство, мы и начнем изложение курса с этого метода. Приведем не-
сколько формулировок ММИ. Все они равнозначны, но доказательство
этого факта из-за его сложности мы опустим, чтобы не отпугивать чита-
теля сразу же трудностями технического порядка.
Буквой
N
в дальнейшем мы будем обозначать множество нату-
ральных чисел:
.,...,...,3,2,1 nN
0
N
расширенное множество натуральных чисел, то есть
.,...,...,3,2,1,0
0
nN
Пусть
nP
обозначает некоторое свойство натуральных чисел.
Теорема 1 (стандартный ММИ)
Пусть свойство
P
верно при
1n
и пусть из истинности
при
kn
следует его истинность при
1kn
. Тогда свойство
верно
для любого
Nn
.