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

Математическата индукция е често използван метод за доказване в математиката, най-често когато работим с естествени числа или с някаква друга редица.

Принцип

Основният принцип е, че дадено твърдение доказваме за някакъв първи елемент, при естествените числа най-често това е n = 1. Това доказваме с просто заместване. В следващата, индукционната стъпка доказваме импликацията „ако твърдението е в сила за n = a, то е в сила и за n = a + 1“.

От тези две стъпки можем да заключим, че даденият израз е в сила за всички n (от някакво множество, с което в момента работим). Защо е така? В началото доказваме, че изразът е в сила за n = 1. Същевременно знаем, че ако изразът е в сила за n = a, е в сила и за n = a + 1. Затова избираме a = 1. Знаем, че за a = 1 изразът е в сила и също знаем, че е в сила за a + 1 = 2. В този момент знаем, че изразът е в сила за a = 2. Но тъй като е в сила и за a + 1, трябва да е в сила и за 2 + 1 = 3. И така нататък.

Първи пример

Първият пример ще е тривиален. Ще докажем, че ако към което и да е четно число прибавим две, отново получаваме четно число. Тъй като се движим в естествените числа, записваме общо четно число като 2n, където n е естествено число. Ако за n заместим което и да е естествено число, в резултата получаваме четно число, това се вижда от пръв поглед. Делимостта се записва с вертикална черта така:

$$2\mid 2n$$

Този запис означава, че числото 2 дели без остатък израза 2n. Щом вече можем да запишем делимостта, можем да запишем и това, което трябва да докажем с математическа индукция.

$$2\mid 2n+2;n\in \mathbb{N}$$

Това трябва да докажем в първия пример, тоест че 2 дели израза 2n + 2 – точно това отговаря на първоначалното словесно условие „ако към което и да е четно число прибавим две, отново получаваме четно число“.

В първата стъпка на индукцията го доказваме за първия елемент, за единицата. Заместваме в израза n = 1:

$$\begin{array}{rcl}2& \mid & 2\cdot 1+2\\ 2& \mid & 4\end{array}$$

Две дели четири без остатък, така че за първия елемент е в сила. След това идва ред на индукционната стъпка, в която трябва да докажем, че ако е в сила за a-тия елемент, е в сила и за (a + 1)-вия елемент. В началото предполагаме, че е в сила нашето предположение, тоест n = a:

$$2\mid 2a+2$$

За този израз предполагаме, че е верен – ще го използваме при построяването на доказателството. Сега искаме да докажем, че

$$2\mid 2(a+1)+2.$$

Какво направихме? На мястото на a написахме (a + 1). Важни са скобите, този израз би бил грешен: 2a + 1 + 2. Не прибавяме единица към целия израз, а наистина правим от a израз с единица по-голям, тоест (a + 1). Израза преобразуваме с разкриване на скобата.

$$\begin{array}{rcl}2& \mid & 2(a+1)+2\\ 2& \mid & 2a+2+2\end{array}$$

Сега една малка отбивка към делимостта. Ако имаме две числа, да кажем p и q, които се делят на някакво число, например r, то и техният сбор се дели на числото r. Така е в сила:

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

Можем да заместим там например числата p = 8, q = 20 и r = 4. Виждаме, че четири дели както 8, така и 20. И също така дели и техния сбор 8 + 20 = 28.

Как ще използваме това в нашия пример? Разделяме дясната страна на числата p и q така:

$$p=2a+2;q=2$$

Числото q, тоест 2, тривиално се дели на две. И изразът p също се дели на две, защото ни го казва предположението. Изразът p точно отговаря на нашето предположение, за което предполагаме, че е вярно. А ако p се дели на две и същевременно q се дели на две, то и техният сбор се дели на две.

Още веднъж за предположението. В началото казахме, че предполагаме, че е в сила

$$2\mid 2a+2.$$

Затова когато по време на построяването на доказателството попаднахме на израза 2a + 2, можехме да кажем за него, че се дели на две. Именно защото това е нашето предположение. Това обикновено е най-трудната стъпка на математическата индукция – да разбереш кога и защо може да се използва индукционното предположение.

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

Ако искаш, можеш да го разложиш по друг начин и да не използваш предположението. p = 2n и q = 2 + 2. Числото q = 4 тривиално се дели на две и също така p = 2n, защото след делението на две ни остава числото n, което е естествено, тоест цяло. Отново получихме два израза, които и двата се делят на две, така че и техният сбор се дели на две.

И в двата случая обаче доказахме, че

1. даденият израз е в сила за n = 1,
2. ако изразът е в сила за n, то е в сила и за n + 1.

Оттук вече можем да изведем:

• Знаем, че изразът е в сила за n = 1.
• Ако е в сила за n, трябва да е в сила и за n + 1, тоест и за 1 + 1, тоест изразът е в сила и за n = 2.
• Ако е в сила за n, трябва да е в сила и за n + 1, тоест и за 2 + 1, тоест изразът е в сила и за n = 3.
• Ако е в сила за n, трябва да е в сила и за n + 1, тоест и за 3 + 1, тоест изразът е в сила и за n = 4.
• Ако е в сила за n, трябва да е в сила и за n + 1, тоест и за 4 + 1, тоест изразът е в сила и за n = 5.
• …

Втори пример

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

$$2^n\ge 2n;n\in \mathbb{N}.$$

Първо първата стъпка, проверяваме дали твърдението е в сила за n = 1 като първи елемент на естествените числа, от които избираме n.

$$\begin{array}{rcl}{2}^1& \ge & 2\cdot 1\\ 2& \ge & 2\end{array}$$

Това тривиално е в сила. Сега преминаваме към индукционната стъпка, в която трябва да проверим дали когато е в сила за n = a, е в сила и за n = a + 1. Така нашето предположение е, че е в сила

$$2^a\ge 2a$$

и искаме да докажем:

$$2^{a+1}\ge 2(a+1)$$

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

$$2\cdot 2^a\ge 2a+2$$

В лявата страна вместо умножение използваме събиране, дясната оставяме без промяна.

$$2^a+2^a\ge 2a+2$$

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

$$\begin{array}{rcl}{2}^a& \ge & 2a\\ 2^a& \ge & 2.\end{array}$$

Първият ред следва от предположението, а второто съждение е тривиално (най-малкото 2^a е за a = 1 и то е равно точно на две). Така знаем, че в лявата страна и двата израза са по-големи или равни на двата израза в дясната страна. С това доказахме с индукция, че ако изразът е в сила за a, е в сила и за (a + 1), и тъй като изразът е в сила и за единицата, даденият израз е верен.

Трети пример

Ще опитаме да докажем следното твърдение:

$$3\mid n\Rightarrow 3\mid n^2;n\in \mathbb{N}$$

Словесно: ако n се дели на три, то и n² се дели на три. Ако n не се дели на три, то изразът тривиално е в сила (по определението на импликацията), така че ще се занимаваме със случаите, когато n се дели на три. Това ни поражда редицата от естествени числа a_i=3, 6, 9, 12, 15… От този момент нататък ще се движим в тази редица a_i.

Доказателството с индукция започваме с първата стъпка, тоест дали е в сила за първия елемент. Напомням, че се движим в редицата a_i, така че вземаме първия елемент на тази редица, тоест елемента a₁, който е числото 3. За него изразът е в сила:

$$3\mid 3\Rightarrow 3\mid 3^2$$

Сега преминаваме към индукционната стъпка. Виждаме, че редицата a_i може да се запише като 3n, където n е естествено число. Тоест вторият елемент е с три по-голям от предишния и т.н. Сега да предположим, че изразът е в сила за n, и трябва да осигурим да е в сила и за (n + 3), което е правилото, което поражда следващия елемент в редицата, в която се движим. Първо записваме предположението:

$$3\mid n\Rightarrow 3\mid n^2$$

и после това, което искаме да докажем

$$3\mid (n+3)\Rightarrow 3\mid (n+3{)}^2.$$

Разкриваме скобата от другата страна с помощта на формулата:

$$3\mid (n+3)\Rightarrow 3\mid n^2+6n+9.$$

И вече сме почти в целта. В лявата страна имаме израз, който със сигурност се дели на три, защото n според предположението се дели на три (движим се само в числата от редицата a_i) и числото 3 също се дели на три. В дясната страна имаме първо n², което според предположението се дели на три. Всъщност знаем, че n се дели на три и предположението казва, че ако n се дели на три, то и n² се дели на три:

$$3\mid n\Rightarrow 3\mid n^2$$

След това следва изразът 6n, който тривиално се дели на три. Можеш да си го представиш като съкращаване на дроб:

$$\frac{6n}{3}=2n$$

Променливата n е някакво естествено число, така че и произведението 2n ще е естествено число, тоест след делението на три получихме естествено число и изразът 6n следователно трябва да се дели на три. А числото 9 накрая отново се дели на три. Изразът е в сила за първия елемент и за индукционната стъпка, следователно е верен.

Брой на скобите в израз

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

• естествено число,
• ако p е прост израз, то и (p²) е прост израз,
• ако p и q са прости изрази, то и (p + q) е прост израз.

Така прости изрази са: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). А обратно, тези не са прости изрази:

• 1 + 2 → липсват външните скоби,
• (1 + 2 → липсва дясната скоба,
• 13² → липсват външните скоби,
• (1 + 2 + 3) → липсват скоби, правилно записът трябва да е (1 + (2 + 3))

Прост израз може да възникне например така. В началото избираме прост израз (a + b). Сега на мястото на a заместваме прост израз a = (c + d), така че получаваме ((c + d) + b) и на мястото на b заместваме 3: ((c + d) + 3). На мястото на c заместваме 10: ((10 + d) + 3) и накрая на мястото на d заместваме (5²): ((10 + (5²)) + 3). Важно е да спазваме скобите, иначе няма да работи.

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

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

$$j=n;n\in \mathbb{N}.$$

За израза j е в сила, че броят на скобите е нула, тоест първият елемент удовлетворява условието. В индукционната стъпка ще предположим, че имаме два прости израза p и q и че и двата имат четен брой скоби. Тогава трябва да докажем, че и простите изрази (p + q) и (p²) имат четен брой скоби.

Първо събирането. Ще определим още функцията z(q), която връща броя на скобите на израза q. Тогава изразът (p + q) има z(p) + z(q) + 2 скоби. Тоест има с две скоби повече от сбора на скобите на изразите p и q. Според предположението z(p) и z(q) са четни, тоест ако съберем три четни числа, отново получаваме четно число. За този случай твърдението е в сила.

Сега степента. Отново е в сила предположението, че простият израз p съдържа четен брой скоби. Изразът (p²) тогава съдържа z(p) + 2 скоби, тоест отново с две скоби повече от израза p. И в този случай събираме четни числа, резултатът следователно е четен.

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