Математическа индукция: определение, принципи и примери

Математическа индукция: ясно обяснение на дефиницията, принципите и стъпките с илюстративни примери — научете как да доказвате твърдения за естествените числа.

Автор: Leandro Alegsa

Математическата индукция е специален начин за доказване на математически твърдения, които се отнасят за всички естествени числа (или за всички числа от някакъв минимален естествен праг нататък). Интуитивната идея е проста: ако нещо е вярно за първото число и винаги, когато е вярно за някое число, това гарантира, че е вярно и за следващото, то то е вярно за всички последващи числа.

Формален принцип

Класическата (или слабата) математическа индукция се формулира по следния начин:

  • Базов случай: докажете, че твърдението е вярно за най-малкото число в обсега (обикновено n = 1 или някое друго начално n0).
  • Индуктивна стъпка: приемете като индуктивна хипотеза, че твърдението е вярно за едно произволно, но фиксирано естествено число n — това е индукционната променлива — и докажете, че оттук следва, че то е вярно и за {\displaystyle n+1}.

След като базовият случай и индуктивната стъпка са установени, с помощта на „верига“ от аргументи (1 ⇒ 2 ⇒ 3 ⇒ …) заключаваме, че твърдението е вярно за всички числа от началното до безкрай.

Типичен шаблон за писане на индуктивно доказателство

  1. Посочете за коя променлива (обикновено n n) ще правите индукция.
  2. Докажете базовия случай (например за n = 1).
  3. Формулирайте индуктивната хипотеза: „Нека твърдението е вярно за едно произволно n n.“
  4. Доколкото приемате, че е вярно за n, покажете, чрез логика и/или алгебра, че тогава е вярно и за n{\displaystyle n+1}.

Пример 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:

{\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)}

Доказателство:

Първо, твърдението може да се запише като:

{\displaystyle 2\sum _{k=1}^{n}k=n(n+1)} (за всички естествени числа n)

Чрез индукция върху n,

Първо, за n=1:

{\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)} ,

така че това е вярно.

След това приемете, че за някои n=n0 твърдението е вярно. Това означава, че:

{\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)}

Тогава за n=n0 +1:

{\displaystyle 2\sum _{k=1}^{{n_{0}}+1}k}

може да се препише като

{\displaystyle 2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)}

Тъй като {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),}

{\displaystyle 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)}

Следователно доказателството е завършено чрез индукция.

Сумата от вътрешните ъгли на многоъгълник

Математическата индукция често се посочва с начална стойност 0 (вместо 1). Всъщност тя ще работи също толкова добре с различни начални стойности. Ето един пример, когато началната стойност е 3: "Сумата от вътрешните ъгли на n -страничен многоъгълник е {\displaystyle (n-2)180} градуса."

Първоначалната начална стойност е 3, а вътрешните ъгли на триъгълника са {\displaystyle (3-2)180} градуса. Да приемем, че вътрешните ъгли на n -страничен многоъгълник са {\displaystyle (n-2)180} градуса. Добавете един триъгълник, който прави фигурата {\displaystyle n+1}и това увеличава броя на ъглите със 180 градуса {\displaystyle (n-2)180+180=(n+1-2)180} градуса. Тъй като са разгледани както базовият, така и индуктивният случай, доказателството вече е завършено.

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


 

Индуктивно определение

Същата идея може да се използва за дефиниране на набор от обекти, както и за доказване на твърдения за този набор от обекти.

Например можем да определим n братовчеда от първа степен по следния начин:

  • Братовчед от {\displaystyle 1} степен е дете на брат или сестра на родител.
  • Братовчед от {\displaystyle n+1} степен е дете на братовчед от n степен на родител.

Съществува набор от аксиоми за аритметиката на естествените числа, който се основава на математическа индукция. Той се нарича "Аксиоми на Пеано". Неопределените символи са | и =. Аксиомите са

  • | е естествено число.
  • Ако n е естествено число, то {\displaystyle n|} е естествено число.
  • Ако {\displaystyle n|=m|} , тогава {\displaystyle n=m} .

След това може да се определят операциите събиране и умножение и т.н. чрез математическа индукция. Например:

  • {\displaystyle m+|=m|}
  • {\displaystyle m+n|=(m+n)|}

 

Свързани страници

  • Математическо доказателство
  • Доказателство чрез противоречие
 

Въпроси и отговори

В: Какво представлява математическата индукция?


О: Математическата индукция е специален начин за доказване на математическа истина, който може да се използва за доказване, че нещо е вярно за всички естествени числа или положителни числа от определен момент нататък.

В: Как се извършва доказателството чрез индукция?


О: Доказателството чрез индукция обикновено протича, като се посочва, че доказателството ще се извърши върху n, показва се, че твърдението е вярно, когато n е 1, приема се, че твърдението е вярно за всяко естествено число n, и след това се показва, че то е вярно за следващото число (n+1).

Въпрос: Какво означава да се предположи нещо в индуктивна стъпка?


О: Да приемеш нещо в индуктивна стъпка означава да го приемеш за вярно, без да представиш доказателства или доказателство. То служи като отправна точка за по-нататъшно изследване.

В: Какви числа се използват в математическата индукция?


О: Математическата индукция обикновено използва естествени числа или положителни числа от определен момент нататък.

Въпрос: Как се доказва, че нещо е вярно за следващото число (n+1)?


О: За да покажете, че нещо е вярно за следващото число (n+1), трябва първо да докажете, че то е вярно, когато n=1, и след това да използвате предположението си от индуктивната стъпка, за да покажете, че то е вярно и за n+1.


обискирам
AlegsaOnline.com - 2020 / 2025 - License CC3