Принцип на математическата индукция

📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ ISEE Upper Level • Подготовка за американски колеж◆ 📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ ISEE Upper Level • Подготовка за американски колеж◆

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

Математическа индукция
Определение, принцип и решени задачи

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

Математическа индукция 4 разработени задачи Задачи за самостоятелна работа Д-р Атанас Илчев

Как се доказват твърдения за всички естествени числа чрез базова стъпка и индукционен преход

Математическата индукция е един от най-важните методи за доказване в елементарната и дискретната математика. Използваме я, когато трябва да установим, че дадено твърдение е вярно за всяко естествено число \(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}\).

Следствие: Понякога базовата стъпка започва от число \(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}\to\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}\).

Тази форма е особено полезна при задачи за неравенства, където вместо директно да се доказва \(F(k+1)\ge 0\), често се сравняват последователните стойности \(F(k+1)\) и \(F(k)\).

План за решаване на задачи с математическа индукция:
• формулираме ясно твърдението \(S_n\);
• проверяваме базовата стъпка;
• приемаме, че \(S_k\) е вярно за произволно, но фиксирано \(k\);
• записваме какво трябва да докажем за \(k+1\);
• на ключовото място заместваме чрез индукционната хипотеза;
• довеждаме израза до точната формула или неравенство за \(k+1\).

Къде се греши най-често:
• пропуска се базовата стъпка;
• не се записва точно индукционната хипотеза;
• доказва се друго твърдение вместо формулата за \(k+1\);
• прескача се алгебрично преобразуване без обяснение;
• в края не се прави изрично заключението по принципа на математическата индукция.

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

---

Решени задачи

1

Задача 1. Да се докаже, че за всяко естествено число \(n\) е вярно равенството \[ 1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}. \]

▾

Решение

Нека означим с \(S_n\) твърдението \[ 1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}. \] База: при \(n=1\) получаваме \[ 1^2=1=\frac{1\cdot2\cdot3}{6}, \] следователно \(S_1\) е вярно.

Индукционна хипотеза: нека за някое \(k\in\mathbb{N}\) е вярно \[ 1^2+2^2+\cdots+k^2=\frac{k(k+1)(2k+1)}{6}. \] Индукционен преход: трябва да докажем, че \[ 1^2+2^2+\cdots+k^2+(k+1)^2=\frac{(k+1)(k+2)(2k+3)}{6}. \] Заместим сумата до \(k\) чрез хипотезата: \[ 1^2+2^2+\cdots+k^2+(k+1)^2= \frac{k(k+1)(2k+1)}{6}+(k+1)^2. \] Изнасяме \((k+1)\): \[ =(k+1)\left(\frac{k(2k+1)}{6}+k+1\right) =(k+1)\left(\frac{2k^2+k+6k+6}{6}\right). \] Следователно \[ =\frac{(k+1)(2k^2+7k+6)}{6} =\frac{(k+1)(k+2)(2k+3)}{6}. \] Значи \(S_{k+1}\) е вярно. По принципа на математическата индукция формулата е вярна за всяко \(n\in\mathbb{N}\).

2

Задача 2. Да се докаже, че за всяко естествено число \(n\) е вярно равенството \[ 1\cdot2+2\cdot3+\cdots+n(n+1)=\frac{1}{3}n(n+1)(n+2). \]

▾

Решение

Нека \(S_n\) е твърдението \[ 1\cdot2+2\cdot3+\cdots+n(n+1)=\frac{1}{3}n(n+1)(n+2). \] База: за \(n=1\): \[ 1\cdot2=2=\frac{1}{3}\cdot1\cdot2\cdot3. \] Следователно \(S_1\) е вярно.

Индукционна хипотеза: нека \[ 1\cdot2+2\cdot3+\cdots+k(k+1)=\frac{1}{3}k(k+1)(k+2). \] Индукционен преход: трябва да докажем \[ 1\cdot2+2\cdot3+\cdots+k(k+1)+(k+1)(k+2)=\frac{1}{3}(k+1)(k+2)(k+3). \] Заместим сумата до \(k\): \[ \frac{1}{3}k(k+1)(k+2)+(k+1)(k+2). \] Изнасяме общ множител \((k+1)(k+2)\): \[ (k+1)(k+2)\left(\frac{k}{3}+1\right) =(k+1)(k+2)\frac{k+3}{3}. \] Получаваме \[ \frac{(k+1)(k+2)(k+3)}{3}, \] което е точно търсената формула. Следователно \(S_{k+1}\) е вярно, а оттук и равенството е вярно за всяко \(n\in\mathbb{N}\).

3

Задача 3. Да се докаже, че за всяко естествено число \(n\) числото \[ n^3+2n \] се дели на \(3\).

▾

Решение

Нека \(S_n\) е твърдението „\(n^3+2n\) се дели на \(3\)“.

База: за \(n=1\): \[ 1^3+2\cdot1=3, \] а \(3\) се дели на \(3\). Значи \(S_1\) е вярно.

Индукционна хипотеза: нека за някое \(k\) е вярно, че \[ k^3+2k=3m \] за някое цяло число \(m\).

Индукционен преход: разглеждаме \[ (k+1)^3+2(k+1)=k^3+3k^2+3k+1+2k+2. \] Следователно \[ (k+1)^3+2(k+1)=(k^3+2k)+3k^2+3k+3. \] По индукционната хипотеза \(k^3+2k\) е кратно на \(3\), а \[ 3k^2+3k+3=3(k^2+k+1) \] също е кратно на \(3\). Значи и тяхната сума се дели на \(3\). Следователно \(S_{k+1}\) е вярно.

По принципа на математическата индукция числото \(n^3+2n\) се дели на \(3\) за всяко \(n\in\mathbb{N}\).

4

Задача 4. Да се докаже, че за всяко естествено число \(n\ge 7\) е изпълнено неравенството \[ n!>3^n. \]

▾

Решение

Нека \(S_n\) е твърдението \[ n!>3^n,\qquad n\ge 7. \] База: за \(n=7\): \[ 7!=5040,\qquad 3^7=2187, \] следователно \(7!>3^7\). Значи \(S_7\) е вярно.

Индукционна хипотеза: нека за някое \(k\ge 7\) е вярно \[ k!>3^k. \] Индукционен преход: трябва да докажем, че \[ (k+1)!>3^{k+1}. \] Имаме \[ (k+1)!=(k+1)\cdot k!. \] От индукционната хипотеза следва \[ (k+1)!>(k+1)\cdot 3^k. \] Понеже \(k\ge 7\), то \(k+1\ge 8>3\). Следователно \[ (k+1)\cdot3^k>3\cdot3^k=3^{k+1}. \] Значи \[ (k+1)!>3^{k+1}. \] Следователно \(S_{k+1}\) е вярно. По математическа индукция получаваме \[ n!>3^n\quad \text{за всяко } n\ge 7. \]

---

Задачи за самостоятелна работа

Задача 1Докажете, че \(1+2+3+\cdots+n=\frac{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(\frac{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>n^2\) за всяко \(n\ge 5\).

Задача 11Докажете, че \(\sin(\alpha)+\sin(2\alpha)+\cdots+\sin(n\alpha)=\frac{\sin\left(\frac{n\alpha}{2}\right)\sin\left(\frac{(n+1)\alpha}{2}\right)}{\sin\left(\frac{\alpha}{2}\right)}\), когато \(\sin(\alpha/2)\neq 0\).

Задача 12Докажете, че \(1\cdot1!+2\cdot2!+\cdots+n\cdot n!=(n+1)!-1\).

---

Използвана литература

1. 1.Учебни материали по алгебра и дискретна математика за 7.–12. клас — раздели за математическа индукция.
2. 2.Kenneth H. Rosen, Discrete Mathematics and Its Applications — класически примери за доказване с индукция.
3. 3.George Pólya, How to Solve It — стратегии за математическо мислене и доказване.
4. 4.Собствени бележки, примери и задачи към този урок.

Подготовка

• ➤НВО след 7. клас
• ➤ДЗИ и кандидатстудентски изпити
• ➤Текуща подготовка по математика

Формат

• ➤Онлайн уроци за цялата страна
• ➤Индивидуални и групови занимания
• ➤Материали и домашни по теми

Уроци по математика с д-р Атанас Илчев

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

📞 0883 375 433 Viber

Харесва ли ви съдържанието?

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

📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ ISEE Upper Level • Подготовка за американски колеж◆ 📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ ISEE Upper Level • Подготовка за американски колеж◆