Математична індукція - Інформатика, програмування

3.1.1 Математична індукція

Методом математичної індукції називаються затвердження виду:

Нехай змінна n має область N (натуральні числа). Щоб довести перше твердження, достатньо довести два твердження:

(4)

(5)

Перше цих тверджень називається базисом індукції, друге - індукційним кроком. Для доказу другого твердження беруть довільне натуральне число, позначають його якоюсь буквою, скажімо k, і доводять імплікацію:

Як випливає з визначення квантора спільності, довівши це отримаємо (5). Для доказу (6) припускають, що істинна посилка:

і виводять з цього припущення, що її висновок U(k+1). Твердження (7) називається припущенням індукції.

За доказом затвердження (2) базисом індукції є затвердження U(a), індукційним кроком – ("n³a)(U(n)®U(n+1)), припущенням індукції – затвердження U(k), де k – довільне натуральне число більше або дорівнює a.

Іноді затвердження 1 зручно доводити зворотною індукцією. Поворотна індукція - це індукція з базисом U(1), але з індукційним кроком ("n)("m n)(U(m) ® U(n)). Припущенням індукції є ("m

Для доказу тверджень 1-3 часто буває зручною індукція з подвійним базисом, тобто для випадку 1 індукція з базисом U(1) U(2) та індукційним кроком ("n) ((U(n) U U(n+1)) ®U(n+2)) Іноді зручно застосовувати індукцію з потрійним, чотириразовим і т. д. базисом.

Для доказу тверджень виду

(8)

застосовується індукція за двома змінними. Однак, твердження (8) часто вдається звести до індукції за однією змінною. Для цього формуємо як значення змінної m довільне число та позначаємо його а. Доведемотвердження ("n)U(a,n). З цього твердження очевидно випливає (8). Але останнє твердження має вигляд 1 і його можна довести індукцією. При такій схемі n називається індукційною змінною. Кажуть також, що (8) доводиться за n при фіксованому m.

3.1.1 Практичні завдання

1.Потрібно знайти помилку в доказі того, що натуральні числа рівні між собою.

Нехай A змінна із областю визначення R(N) (множини натуральних чисел), n – змінна із областю визначення N (натуральні числа). Позначимо через U(A, n) вислів: «Якщо безліч A містить n елементів, то A немає двох нерівних натуральних чисел». Очевидно, твердження

рівносильно утвердженню завдання.

Доведемо затвердження (1) індукцією по n, причому індукцію будемо застосовувати у її простій формі. Базисом індукції є:

Доведемо (2). Візьмемо довільне MÌN та доведемо

Тим самим буде доведено твердження (2). Але на основі визначення U, (3) стверджує: «Якщо безліч M містить один елемент, то M немає двох нерівних натуральних чисел», що очевидно. Припустимо тепер як припущення індукції, що ("A)U(A,n) вірно для деякого натурального k, тобто, що вірно

і доведемо, що правильно

Тим самим було затвердження (1) буде доведено. Для доказу (5) візьмемо довільне MÍN та доведемо

Тим самим буде доведено (5). На основі визначення U, (6) є твердження: «Якщо безліч M містить k+1 елементів, то M немає двох нерівних натуральних чисел». Щоб довести цю імплікацію, припустимо, що її посилка є вірною. Пронумеруємо як-небудь елементи множини M. Нехай, наприклад:

Доведемо, що у множині M немає двох нерівних натуральних чисел. Тим самим доказ буде закінчено. Розглянемо двадопоміжних множини:

Кожне з них отримано викиданням M одного елемента і, отже, містить k елементів. З припущення індукції (4) U(K,k) – «Якщо безліч K містить k елементів, то K немає двох нерівних натуральних чисел». Але безліч K саме містить k елементів, отже, у ньому немає двох нерівних натуральних чисел. Звідси:

(7)

Використовуємо вкотре припущення індукції (4). Візьмемо тепер як значення A безліч L. Тепер із (4) отримаємо твердження U(L,k), що означає: «Якщо безліч L містить k елементів, то в ньому немає двох нерівних натуральних чисел». Але безліч L містить якраз k елементів, отже, у ньому немає двох нерівних натуральних чисел. Зокрема:

(8)

З (7) і (8) випливає, що M немає двох нерівних натуральних чисел. Доказ закінчено.

---