Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 21
Текст из файла (страница 21)
Оно является также примером использования принципа сведения к абсурду. ТЕОРЕМА 3.19. Не существует такого положительного целого а, что 0 < а < 1. ДОКАЗАТЕЛЬСТВО. Предположим, что такое число существует, и пусть Я— множество всех положительных целых чисел между 0 и 1. Поскольку Я непусто, по аксиоме Х5 множество Я имеет наименьшее положительное целое число, скажем, а. Умножая неравенство 0 < а < 1 на а, получаем О < аз < а. Теперь, поскольку а < 1, имеем аа < 1. Но это противоречит тому факту, что а— наименьшее положительное целое число, которое меньше 1.
Следовательно, В— пустое множество, и не существует положительное целое число между 0 и 1. ° СЛЕДСТВИЕ 3.20. Если Ь вЂ” целое число, то не существует целое число а, обла- дающее свойством Ь < а < Ь+ 1. Аксиомы Х4 и Хб сформулированы для целых чисел, начиная с 1, с продолжением условий на целые числа, большие 1.
Аналогичные теоремы индукции верны для целых чисел, не меньших некоторого целого у, которое может не совпадать с 1. Следующая теорема служит обоснованием индукции по подмножеству целых, не обязательно положительных, чисел. Рлздел З.з. математоческая индукции 137 ТЕОРЕМА 3.21. (Принцип индукции для целых чисел) Пусть Р(п) — высказывание, обладающее свойствами а) Р(у) истинно и б) для произвольного к > 2, если Р(6) истинно, то Р(6+ 1) истинно. Тогда Р(п) истинно для каждого и > 1. ДОКАЗАТЕЛЬСТВО.
Доказательство следует из аксиомы Ы4. Для этого достаточно положить п = 1 — 1' + 1. Далее в примере доказывается утверждение, включающее неравенство. Часто в такой ситуации приходится использовать следующее свойство, сформулированное в теореме 3.11: (а > 6 > О) д (с > а' > О) — ас > 64(. ПРИМЕР 3.22. Используя принцип индукции для целых чисел, нужно доказать, что для любого целого числа и > 4 имеет место неравенство и! > 2". При использовании индукции по п, в данном случае нельзя начинать с и = 1, поскольку утверждение для п = 1 неверно. Начальной точкой должно быть п = 4, т.к.
утверждение неверно также для п = 2 и п = 3. Согласно обозначениям, введенным для принципа индукции для целых чисел, имеем: 4' = 4, Р(и) — утверждение "и.' > 2"". Сначала докажем утверждение для п = 4. При и = 4 имеем 4! = 24 и 24 = 16, так что 4! > 24. По индуктивному предположению имеем Ы > 2". Нам нужно доказать, что (1+1)! > 2"+'. Заметим, что желаемый результат можно получить, если умножить левую часть неравенства на (6+1), а правую — на 2. Поэтому, если мы покажем, что (й+ 1) > 2, то получим Е! > 2" и (й+ 1) > 2 и сможем сделать вывод, что (6+ 1)! > 2"+'.
Поскольку Е > 4, то к > 2. Следовательно, (й+ 1) . к! > 2 2" и (й+ 1)! > 2"+'. Таким образом, и1 > 2" для каждого и > 4. П ° УПРАЖНЕНИЯ п(Зп — 1) 1. Докажите, что 1+4+ 7+10+ +(Зп — 2) = 2 1 1 1 1 1 п 1 3 3 5 5 7 7 9 (2п — 1)(2п+1) 2п+1 3. Докажите, что 1+ 2+ 2 + 2 + + 2" ' = 2" — 1. 4. Докажите, что 1+г+г +г + - +г" 2 3 а-1 1 — т 6. Докажите, что 1+ 3+ 5+ 7+ + (2п — 1) = пз. п2(п+ 1)2 6. Докажите, что 2 1з = 4 п(и + 1)(п + 2) 7. Докажите, что 2; 1(1+ 1) = 4=1 3 8. Для положительного целого числа и определим а" как а' = а и а"+' = а" а. Докажите, что а™4" = а™а".
9. Используя математическую индукцию, докажите, что (аЬ)ь = а"6". 1ЗВ ГЛАВА 3. Логика, целые числа и доказательства Используя математическую индукцию, докажите, что пз > 2п + 1 для п > 3. Используя математическую индукцию, докажите, что 2" > пз для и > 5. Найдите наибольшее множество положительных целых чисел, для которых 2" > п! истинно. Докажите истинность утверждения. Докажите, что каждое целое число п > 8 может быть записано как п = Зк+ 5тп для некоторых неотрицательных целых чисел л и т. Докажите, что для каждого положительного целого числа п > 2 10. 11. 12.
13. 14. 4" (2п)! и+ 1 (и!)2 < 15. 16. 17. Докажите, что для любого целого числа а и положительных целых чисел гп и п имеет место равенство а "= (а™)". Используя математическую индукцию, докажите, что п! > пз для всех и > 6. Используя математическую индукцию, докажите, что 1 — — 1 — — 1 — — .. 1 — — = для п>2. Докажите, что если И~ — непустое подмножество множества Я и существует целое число х такое, что х < зи для всех зи из И~, то И' имеет наименьший элемент. Найдите ошибку в доказательстве того, что все лошади имеют одну и ту же масть. ДОКАЗАТЕПЬСТВО. Для доказательства утверждения покажем, что любые п лошадей имеют одну и ту же масть.
При п = 1 имеется одна лошадь, которая, естественно, имеет такую же масть, как она сама. Для и = к предположим, что любые данные й лошадей имеют одинаковую масть. Предположим, что в загон помещена к+1-я лошадь. Выведем из загона одну лошадь. Теперь в загоне к лошадей, поэтому они имеют одну и ту же масть, Вернем выведенную лошадь в загон и выведем другую лошадь. Опять в загоне й лошадей, поэтому все они имеют одну масть. Итак, все лошади имеют ту же масть, что и те лошади, которые были выведены. Поэтому все 2+1 лошадей имеют одну и ту же масть. Таким образом, все лошади имеют одну и ту же масть.
18. 19. Ц~,А,) О Аьч.ы Определим П,".,А, как П,',А; = Аг и !),+,'А, ("= П,, А;) Г1 Аь+ы Докажите, что =( '= а) (ЦА1ОА= О(А,ПА); б) (ЦА,) = ПА';. 'О=г / 1=1 ~1=1 / 1=1 21. Используя приведенные выше определения, докажите, что а) ( П А;1 Г! А = П (А, Г! А); б) ( П А, ~ = Ц А',. ',г=1 / г=1 ~г=1 / г=г 22.
Докажите, что из первого принципа индукции вытекает принцип полного упорядочения. 20. Определим О,", А, следующим образом: Ц, А, = А| и Ц+, А, = РАЗДЕЛ 3.4. Делимость 139 23. Докажите, что из принципа полного упорядочения вытекает второй принцип индукции. 24. Докажите, что из второго принципа индукции вытекает первый принцип индукции. 25. Метод "бесконечного спуска" используется иногда для доказательства того, что никакое положительное целое число не может обладать некоторым заданным свойством.
Метод заключается в следующем. Предположим, что существует положительное целое число, скажем, аы обладающее каким-то свойством. Теперь образуем второе положительное целое число, скажем, аз, тоже обладающее этим свойством, но такое, что аз < аы Аналогично, образуем положительное целое число аз, обладающее нашим свойством, и такое, что аз < аз, и так далее. Таким образом, получаем "бесконечно убывающую" последовательность аг > аз > аз > ... положительных чисел. Очевидно, что такая последовательность не может существовать. Эта последовательность возникла из предположения о том, что существует положительное целое число, которое меньше произвольного фиксированного числа и обладает заданным свойством. Таким образом, наше предположение ошибочно.
Докажите следующее утверждение, которое подтверждает приведенное выше рассуждение. Предположим, что а) Т вЂ” подмножество Ж. б) Если п Е Т, то существует т Е АГ такое, что т < п и т Е Т. Тогда Т = И. 26. Используя метод бесконечного спуска, докажите, что не существуют положительные целые числа р и д такие, что рз = 39з, путем нахождения положительного числа р' < р такого, что для некоторого положительного числа 9' имеем (р')з = 3(9')з. Можно считать известным тот факт, что, если а и Ь вЂ” положительные целые числа такие, что Ьз = 3 а, то существует положительное целое число 6, обладающее свойством 6 = 3 6.
3.4. ДЕЛИМОСТЬ Многие целые числа можно представить как произведение меньших чисел. Важные характеристики и отношения целых чисел могут быть получены на основе анализа их структуры с точки зрения составляющих множителей. ОПРЕДЕЛЕНИЕ 3.23. Целое число а есть кратное числа 6, если а = 6т для некоторого целого числа т. Ненулевое целое число Ь делит целое число а, что обозначается как Ь | а, если а есть кратное Ь. Целое число Ь, которое делит целое число а, называется делителем числа а. По определению, 9 ~ 27, поскольку 27 = 9 3, но 5 не делит 12, т.к. не существует целого числа т такого, что 12 = 5 .т, Целые числа 1,2,3,4,6 и 12, и только они, являются положительными делителями числа 12.
Целые числа — 1, — 2, — 3, — 4, — 6 и — 12 также являются делителями числа 12. 140 ГПКВА 3. Логика, целые числа и доказательства ТЕОРЕМА 3.24. Пусть а, Ь и с — целые числа. Тогда а) а ~ а для любого а. б) Для любых а, Ь и с из а ! Ь и 6 ! с следует а ) с. в) Для любых а, Ь и с имеем: Ь ! а и Ь ( с тогда и только тогда, когда Ь ! (т. а+ и. с) для всех целых чисел т и п.
ДОКАЗАТЕЛЬСТВО. а) а=а 1. б) Еслиа(биЬ|с,тоЬ=а тис=Ь п.Следовательио,с=Ь п=(а т) и= а (т и)иаэс. в) Допустим, что Ь ( а и Ь ! с. Тогда а = 6 р и с = 6 9 для некоторых целых чисел р и д. Следовательно, т.а+ и с = т. (Ь р) +и. (Ь д) = Ь (т р+ п 9) и Ь ) (т. а+ и с). Обратно, предположим, что 6 ) (т. а+ и. с) для всех целых чисел т и и. Тогда, если т = 1 п = О, имеем Ь ! а.
Если т = О и и=1, имеем 6| с. ТЕОРЕМА 3.2б. Если а и 6 — положительные целые числа и а ) Ь, то а < 6. ДОКАЗАТЕЛЬСТВО. Доказательство следует из пункта (г) теоремы 3.!1. ° СЛЕДСТВИЕ 3.26. Если для положительных целых чисел а и Ь имеем а ( Ь и Ь | а, то а =Ь. ТЕОРЕМА 3.27.
Для целых чисел а и 6, если а ) Ь и Ь | а, то а = 6 или а = — Ь. ДОКАЗАТЕЛЬСТВО. Если а > О и 6 > О, то в силу следствия 3.2б имеем а = Ь. Если а < О и Ь > О, то — а > О и ( — а) ! Ь, и 6 ! ( — а), так что Ь = — а или а = — Ь. Справедливость утверждения теоремы в случае а > О и Ь < О является следствием симметрии. Доказательство случая а < О и 6 < О предоставляется читателю. ° Из приведенных выше теорем следует, что для положительных целых чисел отношение "делит" рефлексивно, аитисимметричио и траизитивио, поэтому оио является частичным порядком иа множестве положительных целых чисел. Обратите внимание, что отношение делимости ие является отношением частичного порядка иа множестве целых чисел, т.к. "делит" ие является иа множестве целых чисел аитисимметричиым отношением.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
