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

(Mathematical induction) -

Математическата индукция доказва общи математически твърдения

Какво е математическа индукция?

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

Математическа индукция (Mathematical induction)

Типична е употребата ѝ за доказване, че дадено твърдение е вярно за всички естествени числа. Това се прави, като се проверява, че твърдението е вярно за числото 1, след което се доказва, че ако твърдението е вярно за някое естествено число, то е вярно и за следващото естествено число.

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

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

• - Основната теорема на аритметиката,
• - Теоремата на Ферма за малки степени,
• - Теоремата на Бернули.

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

Същност

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

• - Твърдение: За всяко естествено число n, твърдението P(n) е вярно.

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

- Основен етап (базис)

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

- Индуктивен етап (индикатор, индуктивна стъпка)

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

Ако горните два етапа са доказани, то твърдението е вярно за всички естествени числа.

Използване

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

• - теорията на числата,
• - комбинаториката,
• - алгебрата,
• - геометрията и др.

Методът се използва за доказване на твърдения от следния вид:

• - Твърдения за свойства на естествените числа:
• - - "За всяко естествено число n, n2 е положително число."
• - - "За всяко естествено число n, 1+2+...+n=n(n+1)/2​"
• - Твърдения за свойства на други множества, равномощни с множеството на естествените числа:
• - - "За всяко цяло число n, n! е положително число."
• - - "За всяко множество от n точки в равнината, има поне две точки, които са на разстояние най-много 1."

Примери

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

- Пример 1)

За да се докаже, че сумата от първите n естествени числа е равна на n(n + 1) / 2, се използва следната схема:

• - - База: За n = 1, Σ(1) = 1 * 2 / 2 = 1.
• - - Индуктивна стъпка: Нека Σ(n) = n(n + 1) / 2 за n = k.

Тогава

• Σ(n + 1) = (k + 1)(k + 2) / 2 = (k + 1) * k / 2 + (k + 1) / 2

От индуктивната хипотеза, k(k + 1) / 2 = Σ(k), така че

• Σ(n + 1) = (k + 1) * k / 2 + (k + 1) / 2 = (k + 1) * (k / 2 + 1 / 2) = (k + 1) * (k + 1) / 2

Тъй като това е равенството, което трябва да се докаже за n = k + 1, индуктивната стъпка е доказана.

- Пример 2)

За да се докаже, че всяко естествено число, което е кратно на 3, е равно на сумата от три естествени числа, които са кратни на 1, се използва следната схема:

• - - База: За n = 3, 3 = 1 + 1 + 1.
• - - Индуктивна стъпка: Нека всяко естествено число, което е кратно на 3, е равно на сумата от три естествени числа, които са кратни на 1, за n = k. Тогава

• 3k = 3 * (k / 3) = (k / 3) + (k / 3) + (k / 3)

Тъй като това е равенството, което трябва да се докаже за n = k + 1, индуктивната стъпка е доказана.

Пример 3)

Докажете, че за всяко естествено число n, n^2 е положително число.

• Основен етап (база):

За n=1, 1^2=1, което е положително число. Следователно, твърдението е вярно за n=1.

• Индуктивен етап (индиктор):

Нека твърдението е вярно за n=k, т.е. k^2 е положително число. Тогава,

• (k+1)^2=k^2+2^(k+1)

От предпоставката, k^2 е положително число. Освен това, 2k е естествено число, което е поне 2. Следователно, (k+1)^2=k^2+2(k+1) е положително число.

• Заключение:

От основния етап и индуктивния етап следва, че твърдението е вярно за всички естествени числа.

Пример 4)

Докажете, че за всяко естествено число n, 1+2+...+n=n(n+1)/2​.

• Основен етап:

За n=1, 1+2+...+1=1(1+1)​/2=1. Следователно, твърдението е вярно за n=1.

• Индуктивен етап:

Нека твърдението е вярно за n=k, т.е. 1+2+...+k=k(k+1)/2​. Тогава,

• 1+2+...+k+k+1=k(k+1)/2​+k+1

От предпоставката, 1+2+...+k=2k(k+1)​ е вярно. Освен това, k+1 е естествено число. Следователно, 1+2+...+k+k+1=k(k+1)/2​+k+1=(k+1)(k+2)/2​ е вярно.

• Заключение:

От основния етап и индуктивния етап следва, че твърдението е вярно за всички естествени числа.

Обобщение

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

-------
Ако темата ви харесва, споделете я с приятели. Ако са възникнали въпроси, задайте ги в коментарите по-долу. След седмица проверете за отговора.
----------------