Математическа индукция: определение, принципи и примери
Математическа индукция: ясно обяснение на дефиницията, принципите и стъпките с илюстративни примери — научете как да доказвате твърдения за естествените числа.
Математическата индукция е специален начин за доказване на математически твърдения, които се отнасят за всички естествени числа (или за всички числа от някакъв минимален естествен праг нататък). Интуитивната идея е проста: ако нещо е вярно за първото число и винаги, когато е вярно за някое число, това гарантира, че е вярно и за следващото, то то е вярно за всички последващи числа.
Формален принцип
Класическата (или слабата) математическа индукция се формулира по следния начин:
- Базов случай: докажете, че твърдението е вярно за най-малкото число в обсега (обикновено n = 1 или някое друго начално n0).
- Индуктивна стъпка: приемете като индуктивна хипотеза, че твърдението е вярно за едно произволно, но фиксирано естествено число
— това е индукционната променлива — и докажете, че оттук следва, че то е вярно и за
.
След като базовият случай и индуктивната стъпка са установени, с помощта на „верига“ от аргументи (1 ⇒ 2 ⇒ 3 ⇒ …) заключаваме, че твърдението е вярно за всички числа от началното до безкрай.
Типичен шаблон за писане на индуктивно доказателство
- Посочете за коя променлива (обикновено n
) ще правите индукция.
- Докажете базовия случай (например за n = 1).
- Формулирайте индуктивната хипотеза: „Нека твърдението е вярно за едно произволно n
.“
- Доколкото приемате, че е вярно за n, покажете, чрез логика и/или алгебра, че тогава е вярно и за
.
Пример 1 — сума на първите n естествени числа
Твърдение: 1 + 2 + … + n = n(n + 1)/2 за всяко n ≥ 1.
Доказателство (индукция):
- Базов случай: за n = 1 имаме лявата страна 1 и дясната 1(1+1)/2 = 1 — вярно.
- Индуктивна стъпка: предположете, че 1 + 2 + … + n = n(n + 1)/2 за някое n ≥ 1. Тогава
1 + 2 + … + n + (n + 1) = [n(n + 1)/2] + (n + 1) = (n + 1)(n/2 + 1) = (n + 1)(n + 1)/2 = (n + 1)(n + 2)/2,
което е формулата със заместена n чрез n + 1. Следователно твърдението е вярно и за n + 1, и по индукция за всички n ≥ 1.
Пример 2 — проста неравенство
Твърдение: за всяко n ≥ 1, 2^n ≥ n + 1.
Доказателство (индукция):
- Базов случай: n = 1, 2^1 = 2 ≥ 2 = 1 + 1 — вярно.
- Индуктивна стъпка: приемаме 2^n ≥ n + 1. Тогава 2^{n+1} = 2·2^n ≥ 2(n + 1) = n + 1 + (n + 1) ≥ n + 2 (тъй като n + 1 ≥ 1). Следователно 2^{n+1} ≥ (n + 1) + 1, т.е. неравенството държи за n + 1.
Силна индукция (пълна индукция)
При силната индукция индуктивната хипотеза допуска, че твърдението е вярно за всички числа до n (а не само за самото n). Формулира се така:
- Базови случаи: доказват се едно или няколко начални числа (например n = 1 и n = 2).
- Индуктивна стъпка: предполагаме, че твърдението е вярно за всички числа ≤ n и използваме това, за да докажем вярността за n + 1.
Силната индукция е еквивалентна на обикновената от логическа гледна точка, но често е по-удобна, когато за да докажете случая n + 1, ви трябват резултати за няколко предишни стойности (например n − 1, n − 2 и т.н.).
Класически пример за използване на силна индукция: всяко цяло число > 1 се факторизира като произведение на прости числа. Базов случай: 2 е просто. Индуктивна стъпка: ако n + 1 е просто, готово; ако не е, то се разлага на a·b с 1 < a, b ≤ n, и по индуктивна хипотеза и a, и b имат прост разложение.
Връзка с принципа на най-малкия елемент (well-ordering principle)
Математическата индукция е логически еквивалентна на принципа на най-малкия елемент: ако множеството от естествени числа, за които твърдението не е вярно, съдържа някакво число, то има най-малко такова число, и това води до противоречие с индуктивността. Тези принципи могат да се използват взаимозаменяемо при доказателства.
Структурна индукция
Структурна индукция е обобщение на идеята за обекти, които се дефинират рекурсивно (като дървета, изрази, списъци и т.н.). Вместо да индикираме по естествено число, доказываме свойството за базовите конструкции и показваме, че ако е вярно за по-малките/подструктурите, то е вярно и за изгражданите от тях по-сложни конструкции.
Чести грешки и съвети
- Не пропускайте базовия случай: ако индуктивната стъпка зависи от по-ниски случаи (например нужни са два начални случая), уверете се, че всички необходими базови случаи са доказани.
- Ясно формулирайте индуктивната хипотеза — какво точно приемате като вярно за n.
- Не използвайте като допускане това, което трябва да докажете за n + 1 (избягвайте кръгова логика).
- Когато формулирате индукцията от n0 нататък (например за всички n ≥ n0), посочете ясно началното ниво и докажете базовия случай за n0 (а при нужда и няколко следващи случая).
Обобщение
Математическата индукция е мощен инструмент за доказване на безброй твърдения, дефинирани рекурсивно или свързани с естествените числа. Ключовите елементи са:
- ясен базов случай,
- коректно формулирана индуктивна хипотеза, и
- строга индуктивна стъпка, чрез която се преминава от n към n + 1.
Използвайте и вариациите на индукцията (силна индукция, структурна индукция), когато задачата го налага — те често улесняват доказателството и правят аргумента по-интуитивен.
Примери за доказателство чрез индукция
Сума на първите n естествени числа
Докажете, че за всички естествени числа n:
Доказателство:
Първо, твърдението може да се запише като:
(за всички естествени числа n)
Чрез индукция върху n,
Първо, за n=1:
,
така че това е вярно.
След това приемете, че за някои n=n0 твърдението е вярно. Това означава, че:
Тогава за n=n0 +1:
може да се препише като
Тъй като
Следователно доказателството е завършено чрез индукция.
Сумата от вътрешните ъгли на многоъгълник
Математическата индукция често се посочва с начална стойност 0 (вместо 1). Всъщност тя ще работи също толкова добре с различни начални стойности. Ето един пример, когато началната стойност е 3: "Сумата от вътрешните ъгли на -страничен многоъгълник е
градуса."
Първоначалната начална стойност е 3, а вътрешните ъгли на триъгълника са градуса. Да приемем, че вътрешните ъгли на
-страничен многоъгълник са
градуса. Добавете един триъгълник, който прави фигурата
и това увеличава броя на ъглите със 180 градуса
градуса. Тъй като са разгледани както базовият, така и индуктивният случай, доказателството вече е завършено.
Съществуват много математически обекти, за които доказателствата чрез математическа индукция работят. Техническият термин е добре подредено множество.
Индуктивно определение
Същата идея може да се използва за дефиниране на набор от обекти, както и за доказване на твърдения за този набор от обекти.
Например можем да определим братовчеда от първа степен по следния начин:
- Братовчед от
степен е дете на брат или сестра на родител.
- Братовчед от
степен е дете на братовчед от
степен на родител.
Съществува набор от аксиоми за аритметиката на естествените числа, който се основава на математическа индукция. Той се нарича "Аксиоми на Пеано". Неопределените символи са | и =. Аксиомите са
- | е естествено число.
- Ако
е естествено число, то
е естествено число.
- Ако
, тогава
.
След това може да се определят операциите събиране и умножение и т.н. чрез математическа индукция. Например:
Свързани страници
- Математическо доказателство
- Доказателство чрез противоречие
Въпроси и отговори
В: Какво представлява математическата индукция?
О: Математическата индукция е специален начин за доказване на математическа истина, който може да се използва за доказване, че нещо е вярно за всички естествени числа или положителни числа от определен момент нататък.
В: Как се извършва доказателството чрез индукция?
О: Доказателството чрез индукция обикновено протича, като се посочва, че доказателството ще се извърши върху n, показва се, че твърдението е вярно, когато n е 1, приема се, че твърдението е вярно за всяко естествено число n, и след това се показва, че то е вярно за следващото число (n+1).
Въпрос: Какво означава да се предположи нещо в индуктивна стъпка?
О: Да приемеш нещо в индуктивна стъпка означава да го приемеш за вярно, без да представиш доказателства или доказателство. То служи като отправна точка за по-нататъшно изследване.
В: Какви числа се използват в математическата индукция?
О: Математическата индукция обикновено използва естествени числа или положителни числа от определен момент нататък.
Въпрос: Как се доказва, че нещо е вярно за следващото число (n+1)?
О: За да покажете, че нещо е вярно за следващото число (n+1), трябва първо да докажете, че то е вярно, когато n=1, и след това да използвате предположението си от индуктивната стъпка, за да покажете, че то е вярно и за n+1.
обискирам