математическа индукция

Методът математическа индукция е често използван метод за доказване свойства, закони в различни природни науки - физика, астрономия, биология, география генетика, медицина и др. Събират се данни от изследвания като се променят един или малък брой параметри, съставя се таблица с резултатите, чертае се номограма, търси се зависимост. Няколко примера. В химията - Менделеев сравнява известните тогава химични елементи по определени критерии и съставя периодичната таблица. Резултат: броят на известните в момента химични елементи е двойно по-голям, но всички те заемат определените им вече места в същата таблица. Развитието на корабоплаването е пряко свързано с навигацията и логаритмичните таблици на Непер. Самото откриване на логаритмите е следствие от съпоставяне на числови редици.

Един от начините за доказателство, чрез индукция, се извършва на няколко етапа:

База: Твърдението се проверява за елемент с номер = 1.

Индуктивна стъпка: Предполага се, че твърдението е вярно за n = k (това е т. нар. индуктивно предположение). Доказва се, че твърдението е вярно за n = k + 1 (това е т. нар. индуктивно заключение).

Пример за индуктивно доказателство на твърдение: стойност на факториел може да се представи като сума от не повтарящи се степени на 2.

1! = 1 = 2^0

2! = 1*2 = 2 = 2^1

3! = 1*2*3 = 6 = 2^2 + 2^1

4! = 1*2*3*4 = 24 = 2^4 + 2^3

5! = 1*2*3*4*5 = 120 = 2^6 + 2^5 + 2^4 + 2^3

6! = 1*2*3*4*5*6 = 720 = 2^9 + 2^7 + 2^6 + 2^4

7! = 1*2*3*4*5*6*7 = 5040 = 2^12 + 2^9 + 2^8 + 2^7+ 2^5 + 2^4

8! = 1*2*3*4*5*6*7*8 = 40320 = 2^15 + 2^12 + 2^11 + 2^10 + 2^8+ 2^7

Проверява се твърдението за първите няколко елемента - 1!, 2! и 3!.

Предполага се, че твърдението е вярно (примерно) за номера 4 и 5 и се извършва проверка за 6!.

Прескачат се няколко номера (индуктивна стъпка) и отново се извършва проверка (примерно) за 10!.

С това твърдението се смята за доказано.

Предходното доказателство не е единствено възможното - направете опит чрез използване на бройни системи. Подобен алгоритъм може да се ползва при изчисляване на факториел.

Най-яркият пример за множество доказателства (или опити за това) е последната теорема на Ферма.

Формулирана за пръв път от Пиер дьо Ферма през 1637 г. (доказателството не е публикувано). Известни са множество непризнати опити. Едва през 1996 Андрю Уайлс (с известна помощ от екип математици) представя проверено доказателство на теоремата.

Друг пример за математическа индукция с достатъчно дълга история. Една обширна тема в математиката е изчисляване на фигурни числа. Ако в древността са използвани прогресии, то в наше време има очевидно достатъчен брой формули с числа на Фибоначи.

Последователните триъгълни числа могат да бъдат изчислени като сума от аритметична прогресия с членове последователните естествени числа: 0 + 1 + 2 + ... + n = n*(n+1)/2.

Проверете следващите редици на Фибоначи (fibonacci, tribonacci, tetranacci) и открийте разликата в крайния резултат за изчислените стойности на триъгълно число:

a(n) = a(n-2) + 2*n - 1;

a(n) = 2*a(n-1) - a(n-2) +1;

a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3);

a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4).

В разглежданите задачи се налага друг подход - откриване на определена закономерност, създаване на работна хипотеза и последователното прилагане на непълна индукция при нейното доказване. За всяка от разглежданите числови редици са възможни най-малко две формули. Рекурентната формула представя (най-често) всеки член на числова редица чрез един/няколко предходни члена и евентуално неговия номер. Вярното решение използва и двете формули, а при тяхното изчисляване да се използват отделни функции - рекурсия и итерация. Накратко: при търсене на правилни рекурентни зависимости в редиците използвайте рекурсивни алгоритми. Предлаганият подход за доказателство се използва в практиката. Всеки нов метод за изчисляване се проверява по следния начин: сравняват се получените междинни и крайни стойности с тези от вече проверен метод.

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