Математическа индукция | специален начин за доказване на математическа истина

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

Нещо, което е вярно за първия случай (базовия случай);
Винаги, когато едно и също нещо е вярно за даден случай, то ще бъде вярно и за следващия случай (индуктивен случай),

след това

Същото важи за всеки случай по индукция.

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

Посочете, че доказателството ще бъде чрез индукция над n {\displaystyle n} . ( n {\displaystyle n} е индукционната променлива.)
Покажете, че твърдението е вярно, когато n {\displaystyle n} е 1.
Да приемем, че твърдението е вярно за всяко естествено число n {\displaystyle n} . (Това се нарича стъпка на индукция.)

След това покажете, че твърдението е вярно и за следващото число, n + 1 {\displaystyle n+1} $n+1$ .

Тъй като е вярно за 1, то е вярно за 1+1 (=2, чрез стъпката на индукцията), след това е вярно за 2+1 (=3), след това е вярно за 3+1 (=4) и т.н.

Примери за доказателство чрез индукция

Сума на първите n естествени числа

Докажете, че за всички естествени числа n:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 ∑ k = 1 n 0 + 1 k = n 0 ( n 0 + 1 ) + 2 ( n 0 + 1 ) = ( n 0 + 1 ) ( n 0 + 2 ) {\displaystyle 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)} $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} -страничен многоъгълник е ( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ градуса."

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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