Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
11
Добавлен:
14.02.2016
Размер:
94.72 Кб
Скачать

Тема 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. Вправи на закріплення матеріалу.

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. Тепер результат слідує з принципу індукції.

Соседние файлы в папке DM