Підручники з Дискретної Математики / DM / dm03
.docТема 3. Натуральні числа
3.1. Конструктивне визначення множини натуральних чисел
Множина натуральних чисел визначається як N = {1, 2, 3, . . .}. Але це визначення не несе в собі найважливіших властивостей натуральних чисел. Наступне ознеачення буде більш складним, але в той же час і більш конструктивним.
Означення. Множина N натуральних чисел визначається наступними чотирма умовами :
(N1) 1 N.
(N2) Якщо n N, тоді наступне число n + 1 також належить N.
(N3) Кожне n N крім 1 є наступним до якогось числа в N.
(WO) Кожна не пуста підмножина N має найменший елемент.
Умова (WO) носить назву принципу впорядкованості.
Щоб пояснити важливість кожної з цих умов відмітимо, що з умов (N1) і (N2) випливає, що N містить 1, 2, 3, . . . . Але цих двох умов недостатньо для того, щоб виключити з множини N такі числа як 5.5. Якщо ж N містить 5.5, то за умовою (N3) N мусить містити також 4.5, 3.5, 2.5, 1.5, 0.5,-0.5,-1.5,-2.5, . . . , і таким чином не міститиме найменшого елементу. Щоб виключити з розгляду ці числа і необхідна умова (WO).
3.2. Індукція
З умови (WO) Випливає принцип індукції. Ми сформулюємо його в формі, зручній для практичного застосування.
ПРИНЦИП МАТЕМАТИЧНОЇ ІНДУКЦІЇ (СЛАБКА ФОРМА). Припустимо, що предикат p(n) задовольняє наступні умови:
(PIW1) p(1) істинно;
(PIW2) p(n + 1) істинно завжди, коли p(n) істинно.
Тоді p(n) істинно для будь якого n N.
Доведення. Припустимо, що принцип не справджується. Тоді підмножина S = {n N : p(n) є хибним} не пуста. По умові (WO) S має найменший елемент, позначимо його n0 . Якщо n0 = 1, тоді (PIW1) не виконується. Якщо n0 > 1, тоді p(n0 - 1) є істинним, а p(n0) хибним, що протирічить (PIW2). _
ПРИНЦИП ІНДУКЦІЇ (СИЛЬНА ФОРМА). Припустимо, що вислів p(n) задовольняє наступні умови:
(PIW1) p(1) істинно;
(PIW2) p(n + 1) істинно завжди, коли p(m) істинно для всіх m n .
Тоді p(n) істинно для будь якого n N.
Доведення. Припустимо, що принцип не справджується. Тоді підмножина S = {n N : p(n) є хибним} не пуста. По умові (WO) S має найменший елемент, позначимо його n0 . Якщо n0 = 1, тоді (PIS1) не виконується. Якщо n0 > 1, тоді p(m) істинно для всіх m n0 - 1 , але p(n0) хибне, що протирічить (PIS2).
3.3. Приклади
В наступних прикладах ми проілюструємо ідеї, що лежать в основі принципу математичної індукції.
Приклад 3.3.1. Доведемо за допомогою принципу індукції, що
для будь якого n N. Нехай p(n) означає вислів, істинність якого треба довести. Легко перевірити, що p(1) істинно. Припустимо тепер, що p(n) істинно, тобто
Тоді
так що p(n + 1) істинно. Із принципу індукції (слабка форма) слідує, що (1) виконується для кожного n N.
Приклад 3.3.2. Доведемо по індукції, що
для кожного n N. Позначимо вислів (2) через p(n) . Легко перевірити, що p(1) істинно. Припустимо тепер, що
істинно. Тоді
так що p(n + 1) істинно. Із принципу індукції (слабка форма) слідує, що (2) виконується для кожного n N.
Приклад 3.3.3. Доведемо по індукції, що 3n > n3 для всіх n > 3. Позначимо через p(n) вираз
Легко перевірити, що p(1), p(2), p(3), p(4) істинні. Припустимо тепер, що n > 3 і p(n) істинно. Тоді 3n > n3. Звідси слідує, що
Із принципу індукції (слабка форма) слідує, що 3n > n3 виконується для кожного n N.
Приклад 3.3.4. Доведемо по індукції знамениту теорему De Moivre , що
для кожного n N.
Зафіксуємо R і позначимо через p(n) пропозицію, істинність якої треба довести. Легко перевірити, що p(1) істинно. Тепер припустимо, що p(n) істинно, тобто
Тоді
так що p(n + 1) істинно. Із принципу індукції (слабка форма) слідує, що формула виконується для кожного n N.
Приклад 3.3.5. Розглянемо послідовність x1, x2, x3, . . . , задану як x1 = 5, x2 = 11 і
коли n 2. Довести по індукції, що
(5) xn = 2n+1 + 3n-1
для кожного n N.
Позначимо через p(n) пропозицію, істинність якої треба довести. Легко перевірити, що p(1), p(2) істинні. Припустимо тепер, що n 2 і p(m) істинно для кожного m n , тобто xm = 2m+1 +3m-1 fдля кожного m n. Тоді
так що p(n + 1) істинно. Із принципу індукції (сильна форма) слідує, що формула виконується для кожного n N.
-
Вправи на закріплення матеріалу.
1. Довести по індукції наступні тотожності, де n N:
2. Припустимо, що x 1. Довести по індукції, що
3. Знайти найменше m N таке, що m! 2m. Перевірити, що n! 2n для всіх n N, що задовольняють умову n m.
4. Розглянемо шахову дошку розміром 2n × 2n , як показано на рисунку (для n = 4):
Довести по індукції, що дошку можна суцільно покрити фігурами, утвореними трьома клітинками, показаними збоку.
5. Послідовність an визначена рекурсивно для кожного n N як a1 = 3, a2 = 5 і
an = 3an-1 - 2an-2 якщоr n 3. Довести, що an = 2 n + 1 для кожного n N.
6. Для кожного n N і кожного k = 0, 1, 2, . . . , n біноміальний коефіцієнт визначається за формулою
при умові, що 0! = 1.
а) Не використовуючи індукцію показати, що для будь якого k = 1, 2, . . . , n має місце формула
b) Використовуючи формулу, доведену в (a) і принцип індукції довести біноміальну теорему, що для кожного n N
7. Наступна “теорема” являється абсурдом. Знайдіть помилку в “доведенніf”.
Теорема. Нехай L1, L2, … , Ln• ( n 2) різні прямі на площині, жодні дві з яких не паралельні між собою. Тоді всі ці прямі мають спільну точку.
Доведення. Для n = 2 теорема справедлива, тому що дві не паралельні прямі на площині перетинаються. Припустимо, що теорема справедлива для n = k і розглянемо k + 1 прямих L1, L2, … , Lк , Lк+1 . По припущенню k прямих L1, L2, … , Lк мають спільну точку, позначимо її через x. Знову, по припущенню, k прямих L1, L2, … , Lк-1 , Lк+1 мають спільну точку, позначимо її y. Пряма L1 належить обом множинам, тому вона проходить через точки x і y. Пряма Lк-1 також належить обом множинам, тому вона теж проходить через точки x і y. Але прямі L1 і Lк-1 перетинаються лише в одній точці, тому x = y. Значить k + 1 прямих L1, L2, … , Lк , Lк+1 мають спільну точку, а саме точку x. Тепер результат слідує з принципу індукції.