Математическа индукция - Информатика, програмиране
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(n+1))®U(n+2)). Понякога е удобно да се използва индукция с тройна, четворна и т.н. основа.
За доказване на твърдения на формата
(8)
използвайки индукция върху две променливи. Въпреки това, твърдението (8) често може да бъде сведено до индукция върху една променлива. За да направим това, ние формираме произволно число като стойност на променливата m и го обозначаваме като a. Нека докажемтвърдение ("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), вземаме произволен MUN и доказваме
Така (5) ще бъде доказано. Въз основа на дефиницията на U, (6) има твърдение: "Ако множеството M съдържа k + 1 елемента, тогава няма две неравни естествени числа в M." За да докажем тази импликация, нека приемем, че нейната предпоставка е вярна. Изброяваме по някакъв начин елементите на множеството M. Нека например:
Нека докажем, че в множеството M няма две неравни естествени числа. Това ще завърши доказателството. Помислете за двеспомагателни комплекти:
Всеки от тях се получава чрез премахване на един елемент от M и следователно съдържа k елемента. По силата на предположението на индукция (4) U(K,k) – „Ако множеството K съдържа k елемента, то в K няма две неравни естествени числа“. Но множеството K съдържа само k елемента, следователно не съдържа две неравни естествени числа. Оттук:
(7)
Нека отново използваме индуктивното предположение (4). Нека сега вземем множеството L като стойност на A. Сега от (4) получаваме твърдението U(L,k), което означава: „Ако множеството L съдържа k елемента, тогава то не съдържа две неравни естествени числа.“ Но множеството L съдържа само k елемента, следователно не съдържа две неравни естествени числа. В частност:
(8)
От (7) и (8) следва, че в M няма две неравни естествени числа. Доказателството е пълно.