C, PHP, VB, .NET

За първи път задачи с използване на математическа индукция са показани през 17 век от Блез Паскал. Тогава обаче той не е дефинирал явно правило за решаване на такива задачи. Чак през втората половина на 19 век Пеано въвежда "аксиома за математическата индукция". Аксиомите на Пеано за естествените числа гласят следното:

1. Единичният елемент 1∈N;
2. За всяко x∈N съществува еднозначно определен елемент x'∈N наречен "наследник";
3. x'≠1, т.е. единичният елемент не е наследник;
4. Ако за x∈N и y∈N e вярно, че x' = y', то x = y;
5. Ако едно множество M, което е подмножество на N, удовлетворява условията:
   - 1∈M;
   - за всяко x∈M ⇒ x'∈M,
   то M = N (аксиома за математическата индукция).

На базата на петата аксиома се формулира и т.нар. "принцип на математическата индукция". Той се базира на доказване на твърдение P, зависещо от естествен параметър x, т.е. на твърдение P(x). Принципът може да се разгледа чрез следния запис:

P(1)∧ (P(k) → P(k+1)) → P(n), за всяко n∈N. (*)

Типичната употреба е за това да се покаже, че едно твърдение е вярно за всички естествени числа. Ето и най-тривиалният пример:

Зад. 1. Докажете, че всяко n∈N е вярно твърдението, че 1+2+3+...+n = n(n+1)/2

Доказателството на задачи използващи математическа индукция протича в две стъпки. В първата стъпка се доказва, че е вярна т.нар. "база" на индукцията, т.е. трябва да докажем, че е вярно първото твърдение от конюнкцията в (*), а именно P(1). Ето как става това в задача 1:

Решение на зад. 1. Проверяваме дали уравнението е вярно за n=1: 1 = 1*2/2. Базата е потвърдена!

Следва проверка на второто твърдение от конюнкцията в (*), а именно P(k) → P(k+1):

Допускаме, че уравнението е вярно за kЄN, т.е.

1+2+3+...+k = k.(k+1)/2

Добавяме от двете страни на равенството (k+1), с което по вече позната теорема равенството не се променя:

1+2+3+...+k+(k+1) = (k+1) + k.(k+1)/2

но (k+1) + k.(k+1)/2 = (k+1).(1+k/2) = (k+1).(k+2)/2 = (k+1).((k+1)+1)/2

⇒ 1+2+3+...+k+(k+1) = (k+1).((k+1)+1)/2

От това, че сме проверили базата (P(1) е вярно) и сме доказали индукционната стъпка (P(k) → P(k+1)), то по аксиомата приемаме, че твърдението (P(n)) е вярно за всяко nЄN.

Важно е още в самото начало да отбележим, че методът на математическата индукция НЕ е индуктивен метод. Той се основава изцяло на дедуктивни заключения. Припомняме, че индуктивните методи правят заключение за цялото множество на базата на негово подмножество. При математическата индукция ние правим заключението върху цялото множество, т.е. така наречената "пълна индукция".

Математическата индукция е много сложна за усвояване от ученици, а дори и от студенти. Главната причина за това е сложната логическа структура на доказателството. Обикновено в училище не се набляга на задачи използващи математическа индукция, а за тях се дава само обща представа. Изключение правят подготовките с талантливи ученици за математическа олимпиада.

Втората причина е, че системите от аксиоми на Пеано не се дават в явен вид на учениците. Учениците в средния курс на обучение не се запознават с дефинициите на аксиоми, а ги използват подсъзнателно като нещо естествено. Практиката е показала, че в училищния курс по математика е добре аксиомите да се споменават само тогава, когато са нужни, но не и да се структурират предварително преди излагането на останалата теория. Причината е, че при учениците е трудно да се мотивира въвеждане на знание от което не се вижда веднага пряко приложение.

В университетските курсове, когато учениците са "отсяти" и са достигнали високо ниво на мотивация вече материала се поднася по друг принцип, а именно - теорията се изгражда като се започне именно от аксиомите и първичните понятия. Затова и принципите на математическата индукция се разглеждат строго именно в курсовете по математика във висшето образование.

Все пак дори в училище можем сравнително лесно да мотивираме учениците "да преоткриват" методите на математическата индукция. Това става като се направят няколко последователни експеримента (проверки) и накрая се стигне до научно-познавателния метод "обобщение". Ето как можем да го направим например със задача:

Зад. 2. Да се докаже, че за всяко nЄN е вярно равенството:
1 + 3 + 5 + ... + (2n-3) + (2n-1) = n²

При сблъскване за първи път с подобна задача учениците няма да се досетят за проверка на базата. Без да им споменаваме за нея ние можем да мотивираме тази стъпка, като им кажем "нека направим проверка за няколко числа и да видим дали е вярно - да започнем с най-малкото, т.е. 1".

Така последователно проверяваме няколко твърдения: P(1), P(2), P(3), и т.н. Именно така учениците вече се убеждават, че твърдението е вярно за всяко число и непременно някои от тях дори ще твърдят, че задачата е решена. Тук вече учителя трябва да изиска все пак да се направи проверка за всички числа. Така учениците сами ще преоткрият ново затруднение - числата са безкрайно много, т.е. са нужни безкраен брой проверки. Така идва момента за "разкриване на тайната", като учителят казва "Да речем, че сме направили няколко проверки (а ние сме), които са "k" на брой. Ако ние успеем да докажем, че то е вярно и за k+1, то от k+1 ще докажем за k+2, от k+2 ще е вярно за k+3 и така до безкрайност". Така се стига и до втората стъпка от решението:

Примаме, че е вярно за k:

1 + 3 + 5 + ... + (2k-3) + (2k-1) = k²

Добавяме от двете страни на равенството следващото число 2k+1:

1 + 3 + 5 + ... + (2k-1) + (2k+1) = k² + (2k+1)

Но k²+ (2k+1) = (k+1)²

Следователно 1 + 3 + 5 + ... + (2k-1) + (2k+1) = (k+1)²,

тоест доказахме, че от това, че е вярно k следва, че е вярно и за k+1.

Можем да мотивираме индукционната хипотеза и с физичен пример - т.нар. "ефект на доминото". При него ако наредим блокчета домино вертикално едно до друго в редичка и бутнем първото, то ще бутне второто. Да, но второто ще бутне третото. Третото пък ще бутне четвъртото. Ако приемем, че е бутнато "k"-тото, то ще сме сигурни, че то ще бутне и "k+1"-вото. И все пак бъдете внимателни с подобни физични примери - все пак те са върху крайни множества (няма безкрайна редичка домино), а в математическата индукция работим с безкрайно.

Имайте предвид, че е напълно нормално някои от по-слабите ученици въобще да не успеят да усвоят логиката от самото начало. При тях нещата се въвеждат догматично (като процедура, която да следват) и трябва да им се дадат повече еднотипни задачи за упражнение, за да могат постепенно да осъзнаят логиката на стъпките.

Много бързо след започване на решаване на задачите обаче, ще забележите, че учениците няма да са осъзнали защо се прави проверка на базата (n=1). Единствения начин да се мотивира това е чрез очевидни контра примери, в които индукционната стъпка може да се докаже, но базата не е вярна. Ето два примера:

Зад. 3. Вярно ли е, че за всяко x∈N ⇒ x = x+1

Всички ученици веднага ще кажат, че това не е вярно, а то и очевидно не е. Учителят обаче ще настоява да покаже доказателство, а именно:

Приемаме, че равенството е вярно за k, т.е.:

k = k+1

Добавяме от двете страни на равенството числото 1, с което то не се променя:

k+1 = k+1 + 1

⇒ k+1 = k+2

⇒ индукционната стъпка е доказана.

Именно тук показваме на учениците явно необходимостта от първата стъпка (проверка на базата), защото ще покажем, че:

В началото на задачата приехме, че равенството е вярно за k. Защо обаче сме убедени, че сме приели нещо правилно? Нека проверим при най-малкото възможно число, т.е. k=1:

1 = 1+1

Това очевидно не е вярно, т.е. ние сме приели погрешна индукционна хипотеза.

Друг подобен пример, но не чак толкова очевиден за учениците е:

Зад. 4. Вярно ли е, че 2+2²+2³+...+2ⁿ = 2ⁿ⁺¹

Ще видите, че при проверка базата не е вярна (2 не е равно на 4).

Важно е на по-късен етап (след като процедурата е добре изучена и утвърдена) да се покаже и разликата между "пълна" и "непълна" индукция. Така ще покажем на учениците, които все още не са убедени в нуждата от доказване на индукционната хипотеза, че тя е изключително нужна. Тоест трябва да им покажем примери, в които от това, че едно твърдение е вярно за n=1,2,3,4,..., то не е задължително то да е вярно за всяко n. Най-подходящи примери се оказват няколко примера от историята с предположения за простите числа.

Пример 1. Ферма предположил, че 2²ⁿ+1 е просто число. Това е вярно за n=1, 2, 3 и 4, но не е вярно за n=5.

Пример 2. Ойлер доказал, че n²-n+41 е просто число за всяко n<40. При n=40 обаче не е!

Пример 3. Сборът 991.n²+1 не е точен квадрат за всички числа до... n=12055735790331359447442538767

Пример 4. Както знаем всяко число може да се представи като произведение на прости числа. Тези числа, които се представят като произведение на нечетен брой прости числа ще наричаме "нечетен тип", а тези, които се представят като произведение на четен брой числа - "четен тип". Числото "1" приемаме за "четен тип". Например числото 9=3.3 е четен тип, а 30=2.3.5 е нечетен тип. Твърдението, че за всяко N>1 броят на числата от 1 до N, които са нечетен тип, е по-голямо от броя на числата от 1 до N, които са от четен тип, е вярно... до N=906150257 - за него твърдението НЕ е вярно!

Затова и мотивираме нуждата от дедуктивната структура на доказването на индуктивната хипотеза, т.е. да бъдем убедени, че при колкото и да е голямо число n твърдението да е вярно, то винаги е вярно и при n+1.

Ето няколко задачи за упражнение на математическа индукция:

Зад. 5. Докажете, че 1.2.3 + 2.3.4 + ... + n.(n+1).(n+2) = n.(n+1).(n+2).(n+3)/4

Зад. 6. Докажете, че 1² + 3² + 5² + ... + (2n-1)² = n.(2n-1).(2n+1)/3

Зад. 7. Докажете, че 1.2 + 2.3 + 3.4 + 4.5 + ... + n.(n+1) = n.(n+1).(n+2)/3

Зад. 8. Да се докаже, че за всяко естествено число n е вярно, че 11ⁿ⁺² + 12²ⁿ⁺¹ се дели на 133

Зад. 9. Да се докаже, че за всяко естествено число n е вярно, че 2²ⁿ + 15n - 1 се дели на 9

Зад. 10. Да се докаже, че за всяко естествено число n е вярно, че 2ⁿ⁺².3n+ 5n - 4 се дели на 25

Задачите от примерите са взети от книгата "Методика на обучението по математика (обща част), Благоевград 2002".