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

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

Френският математик от XVII век Пиер Ферма, като разглеждал числата 2²¹ + 1 = 5; 2²² + 1 = 17; 2²³ + 1 = 257; 2²⁴ + 1 = 65537 направил извод, че за всяко естествено числото 2²ⁿ + 1 е просто число. Проверката на това твърдение при n = 5 той не могъл да направи, тъй като не успял да си изясни дали числото 2²⁵ + 1 = 4294967297 ма нетривиални делители. По-късно Ойлер успял да покаже, че това число се дели 641, т.е. че 2²⁵ + 1 не е просто число.

Съществуват примери, при които нмерът на експеримента, опрпвергаващ съставена чрез непълна индукция хипотеза, е толкова голям, че да стигне до такава проверка е практически невъзможно. Например, ако разглеждаме числа от вида 99ⁿ² + 1, при естествено n, би могло да се направи извод, че всяко от тях не е точен квадрат. Номерът на експеримента (стойност на n), опровергаващ направения извод, се изразява с число, което се записва с 29 десетични знака. Ясно е, че извършването на такъв брой проверки не е във възможностите даже на бързодействащите електронни сметачни машини.

Разглежданите примери показват, че извод, основан на непълна индукция, може да бъде неверен, затова непълната индукция като метод на изследване трябва да се използва твърде предпазливо. Нейното значение се състои в това, че разглежданото на частни случаи навежда на мисълта за съществуване на една или друга закономерност, което помага да се изкаже хипотеза за характера на тази закономерност. Доказателството на верността й трябва да се извърши по друг начин.

Ако броят на частните случаи е краен и всички те са разгледани, то изводът, направен въз основа на тях, е обоснован. Така например, за да установим броя на простите числа в първата десетица, е достатъчно да разложим на прости множители всички числа от нея. Получаваме 1 = 1; 2 = 2.1; 3 = 3.1; 4 = 4.1 = 2.2; 5 = 5.1; 6 = 6.1 = 2.3; 7 = 7.1; 8 = 8.1 = 4.2 = 2.2.2; 9 = 9.1 = 3.3; 10 = 10.1 = 2.5.
Изводът, че в първата десетица се съдържат 4 прости числа, не изисква допълнителна обосновка.
В този случай сме приложили метод на изследване, про който, изучавайки някакво множество от обекти, ние изследваме всички негови елементи и на тази основа сме направили извод, който е присъщ за разглежданото множество. Този метод се нарича метод на пълната индукция. Заключение, основано на пълна индукция, е напълно достоверно, затова тя (пълната индукция) се използва като метод за строги доказателства.

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

Пример:
Да се докаже, че квадратът на всяко естествено число не може да окончава на 2.
Множеството на естествените числа, което е безкрайно, разбиваме на подмножества в зависимост от последната цифра в десетичния запис на числата, тъй като тя определя последната цифра в десетичния запис на квадрата на разглежданото естествено число. Това най-добре се вижда в следната таблица

Последната цифра в записа
на числото                                   1   2   3   4   5   6   7   8   9   0
Последната цифра в записа
на квадрата на числото               1   4   9   6   5   6   9   4   1   0
Като вземем пред вид втория ред на таблицата, можем да твърдим, че задачата е решена.

В случаите, когато разглежданото множество е безкрайно, но не можем да го разбием на краен брой подмножества, за които да проведем независими изследвания, се прилагат други методи. Един от тях е така наречения метод на математическата индукция. Неогвата основа е една аксиома от теорията на естествените числа, изградена от италианския математик Дж. Пеано (1889г.) Следователно методът на математическата индукция, въпреки своето име, е дедуктивен метод. Аксиомата на Пеано, за която става дума, е известна още под названието "аксиома на математичексата индукция" (принцип на математическата индукция). Една нейна формулировка е следната:

Ако множеството М, съставено от естествени числа, съдържа единицата и заедно с всяко число k съдържа и следващото на k число - k+1, то М съдържа висчки естествени числа.
Тъй като тази аксиома изразява едно основно свойство на естествените числа, то методът на математическата индукция, който се основава на нея, е едно средство за доказване на твърдения, зависещи от натурален параметър ( от променлива, която приема само стойности, които са естествени числа). За доказателствени цели този принцип може да се формулира и така:
Ако някакво твърдение T(n), формулирано за естественото число н, e проверено за n = 1 и допускането, че е вярно за някаква стойност на n = k, следва верността му и за n = k + 1, то твърдението е вярно за кое да е естествено число.
Наистина нека М е множеството, съставено от естествените числа, за които T(n) е вярно. По условие единицата принадлежи на М и k принадлежи на М, то и (k+1) принадлежи на М. Тогава, съгласно аксиомата на математическата индукция, M = n., т.е. твърдението T(n) е вярно за всяко естествено число.

При методът на математическата индукция, приложен за доказателството на някаква теорема (формула), се спазват следните етапи:
1. Проверява се верността на теоремата (формулата), за n = 1.
2. Допуска се, че теоремата е вярна за някакво = k и, използвайки това, се доказва, че тя е вярна за n = k + 1.
3. Въз основа на направеното в 1 и 2 и на принципа на математическата индукция се заключава, че тя (теоремата) е вярна за всяко естествено n. Тук се разсъждава по следната схема: Тъй като е доказано, че теоремата, бидейки вярна за n = k, е вярна и за n = k + 1 и е установено, че е вярна за n = 1, то тя ще бъде вярна и за n = 3 и т.н. тя ще бъде вярна за всяко естесвено n.

Пример 1:
Да се докаже, че
$S_n=1.2.3+2.3.4+...+n(n+1)(n+2)=\frac{n(n+1)(n+2)(n+3)}{4}$
1. При n = 1 имаме S₁ = 1.2.3 = 6; $S_1=\frac{1(1+1)(1+2)(1+3)}{4}=6$
2. Допускаме, че за n = k формулата е вярно, т.е.
$S_k=1.2.3+2.3.4+...+k(k+1)(k+2)=\frac{k(k+1)(k+2)(k+3)}{4}$ е вярно равенство. Ще докажем, че формулата е вярна и за n = k + 1, т.е.:
$S_{k+1}=1.2.3+2.3.4+...+k(k+1)(k+2)+(k+1)(k+2)(k+3)=\frac{(k+1)(k+2)(k+3)(k+4)}{4}.$ Наистина, като заместим в лявата страна на последното равенство 1.2.3 + 2.3.4 + .... + k(k + 1)(k + 2) с равното му според направеното допускане, ще получим: $\frac{k(k+1)(k+2)(k+3)}{4}+(k+1)(k+2)(k+3)=\frac{k(k+1)(k+2)(k+3)+4(k+1)(k+2)(k+3)}{4}=\frac{(k+1)(k+2)(k+3)(k+4)}{4}$, т.е. $1.2.3+2.3.4+...+(k+1)(k+2)(k+3)=\frac{(k+1)(k+2)(k+3)(k+4)}{4}$.
3. Тъй като доказахме, че ако разглежданата формула е вярна за n = k, тя е вярна и за n = k + 1 и проверихме, че е вярна за n = 1, тя ще бъде вярна и зa n = 1 + 1 = 2; n = 2 + 1 = 3 и т.н. ще бъде вярна за всяко n.

Пример 2:
Да се докаже, че за всяко естествено n, 11ⁿ⁺² + 12²ⁿ⁺¹ се дели на 133.
1. При n = 1, 11¹⁺² + 12²⁺¹ = 11³ + 12³ = 3059 = 133.23.
2. Нека при n = k; 11^k+2 + 12^2k+1 = 133p (p e цяло). Тогава при n = k + 1 имаме: 11^k+1+2 + 12^2(k+1)+1 = 11^k+3 + 12²12^2k+1 = 11(11^k+2 + 12^2k+1) + 133.12^2k+1 = 11.133p + 133.12^2k+1 = 133(11p + 12^2k+1).
3. Доказахме, че ако при n = k даденият израз се дели на 133, то налице е същото и при n = k + 1. Тъй като при n = 1 той се дели на 133, съгласно принципа на математическата индукция. той се дели на 133 за всяко естествено n.

Пример 3:
Да се докаже, че броят на подмножествата на множеството M_n = {a₁, a₂, ....., a_n} е равен на 2ⁿ.
1. При n = 1, М₁ = {a₁} и подмножествата на М₁ са празното множество и самото множество M₁, т.е. техният брой е 2¹.
2. Нека n = k, т.е. M_k = {a₁, a₂, ...., a_k}. Допускаме, че броят на подмножествата на M_k е равен на 2^k. Да намерим броя на подмножествата на M_k+1 = {a₁, a₂,.....,a_k+1}.
Всички подмножества на M_k+1 (тия, които съдържат елементита a_k+1) могат да се получат, като към всяко подмножество на M_k се включи елемента а_k+1, т.е. техният брой е също 2^k. Тогава броя на всички подмножества на M_k+1 се получава 2^k + 2^k = 2.2^k = 2^k+1. 3. Съгласно принципа на математическата индукция броят на подмножествата на M_n = {a₁, a₂,....,a_n} е равен на 2ⁿ.

В приложенията често се използва и следната формулировка на принципа на математическата индукция:
Нека m е цяло положително число. Твърдението T(n) е вярно за всяко естествено число n ≥ m, ако T(m) е вярно и от верността на T(k) следва верността на Т(k+1), където k ≥ m.
В този си вид принципът на математическата индукция се използва за доказване на твърдения T(n), където n e естествено число и n ≥ m. В тези случаи първият етап се състои в проверка на твърдението Т(n) за n = m.

Пример 4:
1. При n = 3 получаваме 2³= 8 > 7 = 2.3 + 1
2. Нека твърдението е вярно при n = к ≥ 3, т.е. е изпълнено неравенството 2^k+1 > 2(k + 1). Ще докажем, че е вярно и неравенството 2^k+1 > 2(k + 1) + 1.
      Действително: 2^k+1 = 2^k + 2^k > 2 + 2^k > 2 + 2k + 1 = 2(2k + 1) + 1, т.е.
                        2^k+1 > 2(k + 1) + 1
3. Съгласно принципа на математическата индукция (последната формулировка) неравенството 2ⁿ > 2n + 1 е вярно за всяко естествено число n ≥ 3.

В разгледаните примери показахме някои приложения на математическата индукция за доказване на твърдения, зависещи от натурален параметър. При математически изследвания обаче често се налага най-напред да се открие съществуваща закономерност, да се формулира съответното твърдение за нея и накрая да се докаже верността му за всяко естествено n. При такива случаи понякога се използва последователното прилагане на метода на непълната индукция и метода на математическата индукция. Първият метод се иползва за съзадаване на хипотеза за съществуващата закономерност, открита на основата на разгледани частни случаи. За да се докаже верността на създадената хипотеза, т.е. тя да се отнесе за всички възможни случаи (индукцията да "стане" пълна), се използва вторият метод. В такива случаи понякога се казва, че е приложен методът на пълната математическа индукция.
Приложението на този метод предполага преминаване през следните етапи:
1. Опит и наблюдение.
2. Създаване на хипотеза.
3. Обосноваване на хипотезата.
Това ще покажем в следния пример.

Пример 5:
Да се намери сумата на първите n нечетни естествени числа.
Кратката формулировка на задачата трябва да се разбира в следния смисъл: да се намери по-компактна (по-удобна) формула за пресмятане на споменатата сума, отколкото непосредственото събиране.
1 етап. Да означим с S_n търсената сума, т.е.
            S_n = 1 + 3 + ... + 2n-2
Presmqtame S_n за няколко последователни естествени числа като започнем от единицата S₁ = 1; S₂ = 1 + 3 = 4; S3 = 1 + 3 + 5 = 9; S₄ = 1 + 3 + 5 + 7 = 16 и т.н. Резултатите от пресмятанията на тези частни случаи за удобство представяме в таблица

Задачи

1. Да се докажем че за всяко n естествено число е вярно;

a) $\frac{1}{1.3}+\frac{1}{3.5}+\frac{1}{5.7}+...+\frac{1}{(2n-1)(2n+1)}=\frac{n}{2n+1};$

b) $\frac{1}{1.4}+\frac{1}{4.7}+\frac{1}{7.10}+...+\frac{1}{(3n-2)(3n+1)}=\frac{n}{3n+1}$

c) $\frac{1}{a(a+1)}+\frac{1}{(a+1)(a+2)}+\frac{1}{(a+2)(a+3)}+...+\frac{1}{(a+n-1)(a+n)}=\frac{n}{a(a+n)}$, при а > 0;

d) 2³ⁿ - 7n - 1 се дели на 49;
e) 2²ⁿ + 15n - 1 се дели на 9;
f) 2ⁿ⁺².3n + 5n - 4 се дели на 25.