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

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

Твърдение: $1 + 3 + 5 + \dots + (2n – 1) = n^2$

Решение:

За $n = 1$:

Лявата страна е $1$. Дясната страна е $1^2 = 1$.

Твърдението е вярно за $n = 1$.

 

Допускаме, че твърдението е вярно за $n = k$:

$1 + 3 + 5 + \dots + (2k – 1) = k^2$

Трябва да докажем, че е вярно за $n = k + 1$:

$1 + 3 + 5 + \dots + (2k – 1) + (2(k + 1) – 1) = (k + 1)^2$

Заместваме сумата до $k$ съгласно нашето допускане:

$k^2 + (2k + 2 – 1) = k^2 + 2k + 1$

Знаем, че $k^2 + 2k + 1 = (k + 1)^2$.

Твърдението е доказано.

2. Делимост на израз

Твърдение: Изразът $A_n = n^3 + 2n$ се дели на $3$ за всяко $n \in \mathbb{N}$.

Решение:

За $n = 1$:

$A_1 = 1^3 + 2 \cdot 1 = 3$. Числото $3$ се дели на $3$.

Твърдението е вярно.

 

Допускаме, че за $n = k$, $k^3 + 2k$ се дели на $3$ (т.е. $k^3 + 2k = 3m$, където $m$ е цяло число).

Проверяваме за $n = k + 1$:

$A_{k+1} = (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(m + k^2 + k + 1)$

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

3. Неравенство на Бернули

Твърдение: $(1 + x)^n \ge 1 + nx$ за всяко $x > -1$ и $n \in \mathbb{N}$.

Решение:

За $n = 1$:

$(1 + x)^1 \ge 1 + 1 \cdot x \Rightarrow 1 + x \ge 1 + x$.

Твърдението е вярно.

 

Допускаме, че $(1 + x)^k \ge 1 + kx$.

Трябва да докажем за $n = k + 1$:

$(1 + x)^{k+1} = (1 + x)^k \cdot (1 + x)$

Тъй като $x > -1$, то $(1 + x) > 0$, можем да умножим двете страни на нашето допускане:

$(1 + x)^{k+1} \ge (1 + kx)(1 + x)$

$(1 + x)^{k+1} \ge 1 + x + kx + kx^2$

$(1 + x)^{k+1} \ge 1 + (k + 1)x + kx^2$

Тъй като $kx^2 \ge 0$, то:

$1 + (k + 1)x + kx^2 \ge 1 + (k + 1)x$

Следователно $(1 + x)^{k+1} \ge 1 + (k + 1)x$.

4. Сума от факториели

Твърдение: $1 \cdot 1! + 2 \cdot 2! + \dots + n \cdot n! = (n + 1)! – 1$

Решение:

За $n = 1$:

Лявата страна: $1 \cdot 1! = 1$.

Дясната страна: $(1 + 1)! – 1 = 2! – 1 = 2 – 1 = 1$.

Твърдението е вярно.

 

Допускаме за $n = k$: $1 \cdot 1! + \dots + k \cdot k! = (k + 1)! – 1$

За $n = k + 1$:

$( (k + 1)! – 1 ) + (k + 1) \cdot (k + 1)!$

$= (k + 1)! \cdot (1 + (k + 1)) – 1$

$= (k + 1)! \cdot (k + 2) – 1$

$= (k + 2)! – 1$

Твърдението е доказано.

5. Сума от степени на двойката

Твърдение: $1 + 2 + 2^2 + \dots + 2^{n-1} = 2^n – 1$

Решение:

За $n = 1$:

$2^{1-1} = 2^0 = 1$. Дясната страна е $2^1 – 1 = 1$.

Твърдението е вярно.

 

Допускаме за $n = k$: $1 + 2 + \dots + 2^{k-1} = 2^k – 1$.

Добавяме следващия член $2^k$ към двете страни:

$(1 + 2 + \dots + 2^{k-1}) + 2^k = (2^k – 1) + 2^k$

$= 2 \cdot 2^k – 1$

$= 2^{k+1} – 1$

Твърдението е вярно за $n = k + 1$.

 

Основни задачи

1. $1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$

2. $1 + 3 + 5 + \dots + (2n-1) = n^2$

3. $2 + 4 + 6 + \dots + 2n = n(n+1)$

4. $1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}$

5. $1 \cdot 2 + 2 \cdot 3 + \dots + n(n+1) = \frac{n(n+1)(n+2)}{3}$

6. $n^2 + n$ се дели на $2$.

7. $n^3 – n$ се дели на $6$.

8. $4^n – 1$ се дели на $3$.

9. $5^n – 1$ се дели на $4$.

10. $1 + 5 + 9 + \dots + (4n-3) = n(2n-1)$

11. $1 + 4 + 7 + \dots + (3n-2) = \frac{n(3n-1)}{2}$

12. $2^1 + 2^2 + \dots + 2^n = 2^{n+1} – 2$

13. $(1 + 1)(1 + \frac{1}{1})(1 + \frac{1}{2}) \dots (1 + \frac{1}{n}) = n + 1$

14. $n < 2^n$ за всяко $n \ge 1$.

15. $1 + 2 + 2^2 + \dots + 2^{n-1} = 2^n – 1$

Нека минем към по-сложни и интересни задачи:

Пример 1: делимост на израз с по-висока степен

Твърдение: Изразът $A_n = 9^n – 8n – 1$ се дели на $64$ за всяко $n \in \mathbb{N}$.

Решение:

За $n = 1$:

$A_1 = 9^1 – 8(1) – 1 = 0$. Числото $0$ се дели на $64$.

За по-голяма сигурност при $n = 2$:

$A_2 = 9^2 – 8(2) – 1 = 81 – 16 – 1 = 64$. Твърдението е вярно.

 

Допускаме, че $9^k – 8k – 1 = 64m$ за някое цяло число $m$.

Трябва да докажем за $n = k + 1$:

$A_{k+1} = 9^{k+1} – 8(k + 1) – 1$

$= 9 \cdot 9^k – 8k – 8 – 1$

$= 9(64m + 8k + 1) – 8k – 9$ (от допускането $9^k = 64m + 8k + 1$)

$= 9 \cdot 64m + 72k + 9 – 8k – 9$

$= 9 \cdot 64m + 64k = 64(9m + k)$

Тъй като изразът се дели на $64$, твърдението е доказано.

Пример 2: сума от квадратите на числата на Фибоначи

Твърдение: Ако $F_n$ са числата на Фибоначи ($F_1=1, F_2=1, F_{n}=F_{n-1}+F_{n-2}$), то:

$F_1^2 + F_2^2 + \dots + F_n^2 = F_n \cdot F_{n+1}$

Решение:

За $n = 1$:

$F_1^2 = 1^2 = 1$.

$F_1 \cdot F_2 = 1 \cdot 1 = 1$.

Твърдението е вярно.

 

Допускаме, че $F_1^2 + \dots + F_k^2 = F_k \cdot F_{k+1}$.

За $n = k + 1$ имаме:

$(F_1^2 + \dots + F_k^2) + F_{k+1}^2 = F_k \cdot F_{k+1} + F_{k+1}^2$

$= F_{k+1}(F_k + F_{k+1})$

От дефиницията на числата на Фибоначи знаем, че $F_k + F_{k+1} = F_{k+2}$.

Следователно сумата е $F_{k+1} \cdot F_{k+2}$, което трябваше да се докаже.

Пример 3: неравенство за n-та степен

Твърдение: $2^n > n^2$ за всяко естествено число $n \ge 5$.

Решение:

Тъй като условието е за $n \ge 5$, проверяваме за $n = 5$:

$2^5 = 32$, $5^2 = 25$.

$32 > 25$ е вярно.

 

Допускаме, че $2^k > k^2$ при $k \ge 5$.

Трябва да докажем, че $2^{k+1} > (k + 1)^2$:

$2^{k+1} = 2 \cdot 2^k > 2 \cdot k^2$

За да завършим доказателството, трябва да проверим дали $2k^2 > (k + 1)^2$.

$2k^2 > k^2 + 2k + 1 \Leftrightarrow k^2 – 2k – 1 > 0$

Корените на $k^2 – 2k – 1 = 0$ са $1 \pm \sqrt{2}$. Тъй като $k \ge 5$, параболата е положителна и неравенството $k^2 – 2k – 1 > 0$ е винаги изпълнено.

Следователно $2^{k+1} > (k + 1)^2$.

Пример 4: области в равнината, разделени от прави

Твърдение: $n$ прави в равнината (никои две не са успоредни и никои три не се пресичат в една точка) разделят равнината на $R_n = \frac{n^2 + n + 2}{2}$ области.

Решение:

За $n = 1$:

$R_1 = \frac{1^2 + 1 + 2}{2} = 2$. Една права разделя равнината на две полуравнини. Вярно.

 

Допускаме, че $k$ прави разделят равнината на $\frac{k^2 + k + 2}{2}$ области.

Когато добавим $(k+1)$-вата права, тя пресича всички предишни $k$ прави в $k$ различни точки. Тези $k$ точки разделят новата права на $k+1$ сегмента (лъчи и отсечки). Всеки сегмент преминава през съществуваща област и я разделя на две, добавяйки точно една нова област.

$R_{k+1} = R_k + (k + 1)$

$R_{k+1} = \frac{k^2 + k + 2}{2} + (k + 1) = \frac{k^2 + k + 2 + 2k + 2}{2}$

$R_{k+1} = \frac{(k^2 + 2k + 1) + (k + 1) + 2}{2} = \frac{(k+1)^2 + (k+1) + 2}{2}$

Формулата е доказана.

Пример 5: сума от редица с факториели и степени

Твърдение: $\sum_{i=1}^n i \cdot 2^i = (n – 1)2^{n+1} + 2$

Решение:

За $n = 1$:

Лявата страна: $1 \cdot 2^1 = 2$.

Дясната страна: $(1 – 1)2^{1+1} + 2 = 0 + 2 = 2$.

Твърдението е вярно.

 

Допускаме за $n = k$: $\sum_{i=1}^k i \cdot 2^i = (k – 1)2^{k+1} + 2$.

За $n = k + 1$:

$S_{k+1} = S_k + (k + 1)2^{k+1}$

$= (k – 1)2^{k+1} + 2 + (k + 1)2^{k+1}$

$= 2^{k+1}(k – 1 + k + 1) + 2$

$= 2^{k+1}(2k) + 2$

$= k \cdot 2^{k+2} + 2$

Тъй като $( (k+1) – 1 )2^{(k+1)+1} + 2 = k \cdot 2^{k+2} + 2$, твърдението е доказано.

Средни задачи

16. $1^3 + 2^3 + \dots + n^3 = (\frac{n(n+1)}{2})^2$

17. $\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \dots + \frac{1}{n(n+1)} = \frac{n}{n+1}$

18. $1 \cdot 1! + 2 \cdot 2! + \dots + n \cdot n! = (n+1)! – 1$

19. $7^n + 3n – 1$ се дели на $9$.

20. $10^n – 1$ се дели на $9$.

21. $11^n – 4^n$ се дели на $7$.

22. $2^{3n} – 1$ се дели на $7$.

23. $3^{2n+1} + 2^{n+2}$ се дели на $7$.

24. $1^2 + 3^2 + 5^2 + \dots + (2n-1)^2 = \frac{n(4n^2-1)}{3}$

25. $\frac{1}{1 \cdot 3} + \frac{1}{3 \cdot 5} + \dots + \frac{1}{(2n-1)(2n+1)} = \frac{n}{2n+1}$

26. $2n + 1 < 2^n$ за $n \ge 3$.

27. $n^3 + (n+1)^3 + (n+2)^3$ се дели на $9$.

28. $x^n – y^n$ се дели на $(x-y)$ за всяко $x \neq y$.

29. $3^n > n^2$ за всяко $n \ge 1$.

30. $\sum_{i=1}^n \frac{i}{2^i} = 2 – \frac{n+2}{2^n}$

 

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

1. Брой на ребрата в дърво

Твърдение: Всеки свързан граф без цикли (дърво) с $n$ върха има точно $n – 1$ ребра.

Решение:

За $n = 1$: Граф с един връх няма ребра. $1 – 1 = 0$. Твърдението е вярно.

 

Допускаме, че всяко дърво с $k$ върха има $k – 1$ ребра. Нека разгледаме дърво $T$ с $k + 1$ върха.

Всяко дърво с поне два върха има поне два „листа“ (върхове от степен 1). Нека $v$ е такъв лист и $e$ е единственото ребро, свързано с него.

Ако премахнем върха $v$ и реброто $e$, получаваме нов граф $T’$. Тъй като $T$ е било свързано и без цикли, $T’$ също е свързано и без цикли, но има $k$ върха.

Според индукционното допускане $T’$ има $k – 1$ ребра.

Тогава броят на ребрата в $T$ е $(k – 1) + 1 = k$.

Тъй като $n = k + 1$, то $n – 1 = (k + 1) – 1 = k$. Твърдението е доказано.

2. Формула на Ойлер за планарни графи

Твърдение: За всеки свързан планарен граф с $V$ върха, $E$ ребра и $F$ стени (включително външната), е вярно: $V – E + F = 2$.

Решение: (Индукция по броя на ребрата $E$)

Ако $E = 0$, графът е само един връх ($V=1$). Той има само една стена (външната, $F=1$).

$1 – 0 + 1 = 2$. Вярно.

 

Допускаме, че формулата е вярна за граф с $k$ ребра. Нека имаме граф с $k + 1$ ребра.

• Случай 1: Графът е дърво. Тогава $E = V – 1$ и $F = 1$. $V – (V – 1) + 1 = 2$.

• Случай 2: Графът съдържа цикъл. Нека $e$ е ребро от цикъл. Това ребро разделя две стени. Ако го премахнем, броят на ребрата става $k$, а двете стени се сливат в една. Новият граф има $V$ върха, $k$ ребра и $F – 1$ стени.Според допускането: $V – k + (F – 1) = 2$.Заместваме $k = E – 1$: $V – (E – 1) + F – 1 = 2 \Rightarrow V – E + 1 + F – 1 = 2 \Rightarrow V – E + F = 2$.

3. Хамилтонов път в турнир

Твърдение: Във всеки „турнир“ (пълен ориентиран граф) съществува Хамилтонов път (път, минаващ през всеки връх точно веднъж).

Решение:

За $n = 1$ връх, пътят е самият връх. За $n = 2$, има ребро или от $A$ към $B$, или от $B$ към $A$, което е Хамилтонов път.

 

Допускаме, че в турнир с $k$ върха има Хамилтонов път $v_1 \to v_2 \to \dots \to v_k$.

Добавяме нов връх $u$.

1. Ако има ребро $u \to v_1$, новият път е $u \to v_1 \to \dots \to v_k$.

2. Ако няма такова, значи има ребро $v_1 \to u$. Проверяваме следващите върхове. Ако намерим $i$, такова че $v_i \to u$ и $u \to v_{i+1}$, вмъкваме $u$ между тях: $\dots \to v_i \to u \to v_{i+1} \to \dots$.

3. Ако за всички $i$ има ребро $v_i \to u$, новият път е $v_1 \to \dots \to v_k \to u$.Във всички случаи намираме път за $k + 1$ върха.

4. Покриване с L-тромино (задача от олимпиада)

Твърдение: Шахматна дъска с размери $2^n \times 2^n$, от която е премахнато едно произволно квадратче, може да бъде покрита с L-образни фигури от 3 квадратчета (тромино).

Решение:

За $n = 1$ имаме дъска $2 \times 2$. Ако махнем едно квадратче, остават 3, които образуват точно една L-фигура.

 

Допускаме, че можем да покрием дъска $2^k \times 2^k$ с едно липсващо квадратче.

Разглеждаме дъска $2^{k+1} \times 2^{k+1}$. Разделяме я на четири квадранта с размери $2^k \times 2^k$.

Един от тези квадранти съдържа липсващото квадратче. Поставяме една L-фигура в центъра на голямата дъска така, че тя да покрива по едно квадратче от останалите три квадранта (тези, които нямат липсващо квадратче).

Сега и четирите квадранта имат по едно „липсващо“ квадратче (оригиналното или покритите от централната фигура).

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

5. Числа на Фибоначи и суми (теорема на Цекендорф)

Твърдение: Всяко естествено число $n$ може да бъде представено като сума от различни, несъседни числа на Фибоначи.

Решение: (Използваме силна индукция)

За $n = 1$: $1 = F_2$ (или $F_1$).

За $n = 2$: $2 = F_3$.

За $n = 3$: $3 = F_4$.

Всички са числа на Фибоначи, твърдението е вярно.

 

Допускаме, че твърдението е вярно за всички числа, по-малки от $k$.

Нека $F_m$ е най-голямото число на Фибоначи, такова че $F_m \le k$.

Ако $k = F_m$, сме готови.

Ако $k > F_m$, разглеждаме остатъка $x = k – F_m$. Тъй като $x < k$, според допускането $x$ може да се представи като сума от несъседни числа на Фибоначи.

Важно е да докажем, че $F_m$ не е съседно на никое число от сумата на $x$. Най-голямото възможно число в сумата на $x$ трябва да е по-малко от $F_{m-1}$, защото ако $x \ge F_{m-1}$, то $k = F_m + x \ge F_m + F_{m-1} = F_{m+1}$, което противоречи на избора на $F_m$ като най-голямото.

Следователно най-голямото число в $x$ е най-много $F_{m-2}$, което не е съседно на $F_m$.