Принцип на математическата индукция
📞 Онлайн уроци по математика за цялата страна◆
гл.ас. д-р Атанас Илчев◆
Индивидуални и групови уроци • Тел: 0883 375 433◆
Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆
📞 Онлайн уроци по математика за цялата страна◆
гл.ас. д-р Атанас Илчев◆
Индивидуални и групови уроци • Тел: 0883 375 433◆
Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆
Математика › Математическа индукция
Математическа индукция
Определение, принцип и решени задачи
Пълен урок с теория, формулировка на принципа, леми, подробно решени задачи и задачи за самостоятелна работа
Как се доказват твърдения за всички естествени числа чрез базова стъпка и индукционен преход
Математическата индукция е един от най-важните методи за доказване в елементарната и дискретната математика. Използваме я, когато трябва да установим, че дадено твърдение е вярно за всяко естествено число \(n\), за всички суми от определен вид, за делимост, неравенства, рекурентни зависимости и много други.
Идеята е проста и изключително силна: доказваме първия случай, а след това показваме, че ако твърдението е вярно за някое естествено число \(k\), то е вярно и за следващото число \(k+1\). Тази логика често се сравнява с редица от домино — ако първата плочка пада и всяка плочка събаря следващата, тогава пада цялата редица.
По-долу урокът следва класическа структура: дефиниции, леми и основен принцип, план за решаване, най-чести грешки, 4 подробно решени задачи и задачи за самостоятелна работа.
Определения, леми и основен принцип
Определение 1: Нека \(S_1,S_2,S_3,\ldots\) е безкрайна редица от твърдения. Целта ни е да докажем, че всяко твърдение \(S_n\) е вярно за всяко \(n\in\mathbb{N}\).
Определение 2: Базова стъпка наричаме проверката, че първото твърдение \(S_1\) (или съответно \(S_{n_0}\)) е вярно.
Определение 3: Индукционна хипотеза е допускането, че за някое фиксирано \(k\in\mathbb{N}\) твърдението \(S_k\) е вярно.
Определение 4: Индукционен преход е доказателството, че от вярността на \(S_k\) следва вярността на \(S_{k+1}\).
Теорема 1 (Принцип на математическата индукция): Ако са изпълнени следните две условия:
1) твърдението \(S_1\) е вярно;
2) за всяко естествено число \(k\) от \(S_k\) следва \(S_{k+1}\),
то твърдението \(S_n\) е вярно за всяко \(n\in\mathbb{N}\).
1) твърдението \(S_1\) е вярно;
2) за всяко естествено число \(k\) от \(S_k\) следва \(S_{k+1}\),
то твърдението \(S_n\) е вярно за всяко \(n\in\mathbb{N}\).
Следствие: Понякога базовата стъпка започва от число \(n_0\), а не от \(1\). Тогава доказваме \(S_{n_0}\) и после показваме, че за всяко \(k\ge n_0\) от \(S_k\) следва \(S_{k+1}\). Заключението е, че \(S_n\) е вярно за всички \(n\ge n_0\).
Лема 1: Нека \(A_n=\sum_{i=1}^{n} a_i\). Тогава за всяко \(k\in\mathbb{N}\) е изпълнено \(A_{k+1}=A_k+a_{k+1}\). Следователно при доказване на формули за суми с математическа индукция индукционният преход се свежда до замяна на сумата до \(k\) чрез индукционната хипотеза и прибавяне на новия член.
Лема 2: Нека \(F:\mathbb{N} o\mathbb{R}\). Ако \(F(1)\ge 0\) и за всяко \(k\in\mathbb{N}\) е изпълнено \(F(k+1)-F(k)\ge 0\), то \(F(n)\ge 0\) за всяко \(n\in\mathbb{N}\). Тази форма е особено полезна при задачи за неравенства.
План за решаване на задачи с математическа индукция:
• формулираме ясно твърдението \(S_n\);
• проверяваме базовата стъпка;
• приемаме, че \(S_k\) е вярно за произволно, но фиксирано \(k\);
• записваме какво трябва да докажем за \(k+1\);
• на ключовото място заместваме чрез индукционната хипотеза;
• довеждаме израза до точната формула или неравенство за \(k+1\).
• формулираме ясно твърдението \(S_n\);
• проверяваме базовата стъпка;
• приемаме, че \(S_k\) е вярно за произволно, но фиксирано \(k\);
• записваме какво трябва да докажем за \(k+1\);
• на ключовото място заместваме чрез индукционната хипотеза;
• довеждаме израза до точната формула или неравенство за \(k+1\).
Къде се греши най-често:
• пропуска се базовата стъпка;
• не се записва точно индукционната хипотеза;
• доказва се друго твърдение вместо формулата за \(k+1\);
• прескача се алгебрично преобразуване без обяснение;
• в края не се прави изрично заключението по принципа на математическата индукция.
• пропуска се базовата стъпка;
• не се записва точно индукционната хипотеза;
• доказва се друго твърдение вместо формулата за \(k+1\);
• прескача се алгебрично преобразуване без обяснение;
• в края не се прави изрично заключението по принципа на математическата индукция.
Разработени задачи
Кликнете върху задача, за да видите решението.
1
Докажете, че за всяко \(n\in\mathbb{N}\) е вярно \(1^2+2^2+\cdots+n^2=\dfrac{n(n+1)(2n+1)}{6}\).
▼
Решение
База (\(n=1\)): \(1^2=1=\dfrac{1\cdot2\cdot3}{6}\). \(S_1\) е вярно.
Индукционна хипотеза: нека \(1^2+2^2+\cdots+k^2=\dfrac{k(k+1)(2k+1)}{6}\) за някое \(k\in\mathbb{N}\).
Индукционен преход: трябва да докажем \(1^2+\cdots+k^2+(k+1)^2=\dfrac{(k+1)(k+2)(2k+3)}{6}\).
Заместваме сумата до \(k\): \[\frac{k(k+1)(2k+1)}{6}+(k+1)^2=(k+1)\!\left(\frac{k(2k+1)}{6}+k+1\right)=(k+1)\cdot\frac{2k^2+7k+6}{6}=\frac{(k+1)(k+2)(2k+3)}{6}.\] Следователно \(S_{k+1}\) е вярно. По принципа на математическата индукция формулата е вярна за всяко \(n\in\mathbb{N}\). \(lacksquare\)
Индукционна хипотеза: нека \(1^2+2^2+\cdots+k^2=\dfrac{k(k+1)(2k+1)}{6}\) за някое \(k\in\mathbb{N}\).
Индукционен преход: трябва да докажем \(1^2+\cdots+k^2+(k+1)^2=\dfrac{(k+1)(k+2)(2k+3)}{6}\).
Заместваме сумата до \(k\): \[\frac{k(k+1)(2k+1)}{6}+(k+1)^2=(k+1)\!\left(\frac{k(2k+1)}{6}+k+1\right)=(k+1)\cdot\frac{2k^2+7k+6}{6}=\frac{(k+1)(k+2)(2k+3)}{6}.\] Следователно \(S_{k+1}\) е вярно. По принципа на математическата индукция формулата е вярна за всяко \(n\in\mathbb{N}\). \(lacksquare\)
2
Докажете, че за всяко \(n\in\mathbb{N}\) е вярно \(1\cdot2+2\cdot3+\cdots+n(n+1)=\dfrac{1}{3}n(n+1)(n+2)\).
▼
Решение
База (\(n=1\)): \(1\cdot2=2=\dfrac{1}{3}\cdot1\cdot2\cdot3\). \(S_1\) е вярно.
Индукционна хипотеза: нека \(1\cdot2+\cdots+k(k+1)=\dfrac{1}{3}k(k+1)(k+2)\).
Индукционен преход: трябва да докажем \(\dfrac{1}{3}(k+1)(k+2)(k+3)\). \[\frac{1}{3}k(k+1)(k+2)+(k+1)(k+2)=(k+1)(k+2)\!\left(\frac{k}{3}+1\right)=(k+1)(k+2)\cdot\frac{k+3}{3}=\frac{(k+1)(k+2)(k+3)}{3}.\] Следователно \(S_{k+1}\) е вярно и равенството е вярно за всяко \(n\in\mathbb{N}\). \(lacksquare\)
Индукционна хипотеза: нека \(1\cdot2+\cdots+k(k+1)=\dfrac{1}{3}k(k+1)(k+2)\).
Индукционен преход: трябва да докажем \(\dfrac{1}{3}(k+1)(k+2)(k+3)\). \[\frac{1}{3}k(k+1)(k+2)+(k+1)(k+2)=(k+1)(k+2)\!\left(\frac{k}{3}+1\right)=(k+1)(k+2)\cdot\frac{k+3}{3}=\frac{(k+1)(k+2)(k+3)}{3}.\] Следователно \(S_{k+1}\) е вярно и равенството е вярно за всяко \(n\in\mathbb{N}\). \(lacksquare\)
3
Докажете, че за всяко \(n\in\mathbb{N}\) числото \(n^3+2n\) се дели на \(3\).
▼
Решение
База (\(n=1\)): \(1^3+2\cdot1=3\), което се дели на \(3\). \(S_1\) е вярно.
Индукционна хипотеза: нека \(k^3+2k=3m\) за някое цяло \(m\).
Индукционен преход: \[(k+1)^3+2(k+1)=k^3+3k^2+3k+1+2k+2=(k^3+2k)+3k^2+3k+3=3m+3(k^2+k+1).\] Тъй като и двете части се делят на \(3\), сумата им също се дели на \(3\). Следователно \(S_{k+1}\) е вярно. \(lacksquare\)
Индукционна хипотеза: нека \(k^3+2k=3m\) за някое цяло \(m\).
Индукционен преход: \[(k+1)^3+2(k+1)=k^3+3k^2+3k+1+2k+2=(k^3+2k)+3k^2+3k+3=3m+3(k^2+k+1).\] Тъй като и двете части се делят на \(3\), сумата им също се дели на \(3\). Следователно \(S_{k+1}\) е вярно. \(lacksquare\)
4
Докажете, че за всяко \(n\ge7\) е изпълнено неравенството \(n!\gt3^n\).
▼
Решение
База (\(n=7\)): \(7!=5040\) и \(3^7=2187\), следователно \(7!\gt3^7\). \(S_7\) е вярно.
Индукционна хипотеза: нека \(k!\gt3^k\) за някое \(k\ge7\).
Индукционен преход: \[(k+1)!=(k+1)\cdot k!\gt(k+1)\cdot3^k.\] Понеже \(k\ge7\), то \(k+1\ge8\gt3\), следователно \((k+1)\cdot3^k\gt3\cdot3^k=3^{k+1}\).
Получаваме \((k+1)!\gt3^{k+1}\). Следователно \(S_{k+1}\) е вярно и \(n!\gt3^n\) за всяко \(n\ge7\). \(lacksquare\)
Индукционна хипотеза: нека \(k!\gt3^k\) за някое \(k\ge7\).
Индукционен преход: \[(k+1)!=(k+1)\cdot k!\gt(k+1)\cdot3^k.\] Понеже \(k\ge7\), то \(k+1\ge8\gt3\), следователно \((k+1)\cdot3^k\gt3\cdot3^k=3^{k+1}\).
Получаваме \((k+1)!\gt3^{k+1}\). Следователно \(S_{k+1}\) е вярно и \(n!\gt3^n\) за всяко \(n\ge7\). \(lacksquare\)
Задачи за самостоятелна работа
Опитайте да решите сами, преди да потърсите помощ.
Задача 1Докажете, че \(1+2+3+\cdots+n=\dfrac{n(n+1)}{2}\) за всяко \(n\in\mathbb{N}\).
Задача 2Докажете, че \(1+3+5+\cdots+(2n-1)=n^2\).
Задача 3Докажете, че \(1^3+2^3+\cdots+n^3=\left(\dfrac{n(n+1)}{2}\right)^2\).
Задача 4Докажете, че \(2^n\ge n+1\) за всяко \(n\in\mathbb{N}\).
Задача 5Докажете, че \(5^n-1\) се дели на \(4\) за всяко \(n\in\mathbb{N}\).
Задача 6Докажете, че \(8^n-1\) се дели на \(7\) за всяко \(n\in\mathbb{N}\).
Задача 7Докажете, че \(n^2+n\) е четно число за всяко \(n\in\mathbb{N}\).
Задача 8Докажете, че \(n^3-n\) се дели на \(3\) за всяко \(n\in\mathbb{N}\).
Задача 9Докажете, че \(6^n+2\) се дели на \(4\) за всяко \(n\in\mathbb{N}\).
Задача 10Докажете, че \(2^n\gt n^2\) за всяко \(n\ge5\).
Задача 11Докажете, че \(\sin(\alpha)+\sin(2\alpha)+\cdots+\sin(n\alpha)=\dfrac{\sin\!\left(\frac{n\alpha}{2}\right)\sin\!\left(\frac{(n+1)\alpha}{2}\right)}{\sin\!\left(\frac{\alpha}{2}\right)}\) когато \(\sin(\alpha/2)
eq0\).
Задача 12Докажете, че \(1\cdot1!+2\cdot2!+\cdots+n\cdot n!=(n+1)!-1\).
Видео уроци
Свързани уроци
▶
Числови редици. Граница на числова редица
Монотонност, ограниченост, граница по дефиниция (ε–N), лема за двамата полицаи, основна граница \(e\) — 27 разработени задачи и тест.
Преглед на урока →
Използвана литература
- 1.Учебни материали по алгебра и дискретна математика за 7.–12. клас — раздели за математическа индукция.
- 2.Kenneth H. Rosen, Discrete Mathematics and Its Applications — класически примери за доказване с индукция.
- 3.George Pólya, How to Solve It — стратегии за математическо мислене и доказване.
- 4.Собствени бележки, примери и задачи към този урок.
Запишете урок
Индивидуални и групови онлайн уроци по математика за цялата страна
🎓 Подготовка за изпити
- ›НВО по математика след 7 клас
- ›НВО по математика след 10 клас
- ›Кандидатстудентски изпити по математика
- ›Софийски университет „Св. Климент Охридски“
- ›УАСГ – Университет по архитектура, строителство и геодезия
- ›Технически университет – София и др.
- ›Прием в университети в чужбина (ISEE, SAT, A-Level и др.)
📚 Текущо обучение и студенти
- ›Усвояване на текущия учебен материал (всички класове)
- ›Студенти по всички математически дисциплини:
Математически анализ, Линейна алгебра, Аналитична геометрия, Диференциални уравнения, Теория на вероятностите, Статистика и др.
Харесва ли ви съдържанието?
Ако този урок ви е бил полезен, можете да подкрепите създаването на нови безплатни материали.
📞 Онлайн уроци по математика за цялата страна◆
гл.ас. д-р Атанас Илчев◆
Индивидуални и групови уроци • Тел: 0883 375 433◆
Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆
📞 Онлайн уроци по математика за цялата страна◆
гл.ас. д-р Атанас Илчев◆
Индивидуални и групови уроци • Тел: 0883 375 433◆
Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆
Коментари
Публикуване на коментар