Математическа индукция - задачи с решения

Решение:
Тъй като [tex]1+2+\ldots+n=\frac{n(n+1)}{2}[/tex] (сбор на аритметична прогресия), достатъчно е да докажем, че
[tex]S_{n}=1^{3}+2^{3}+\ldots+n^{3}=\frac{n^{2}(n+1)^{2}}{4}[/tex]
Прилагаме математическа индукция по [tex]n[/tex]. База: при [tex]n=1[/tex] имаме [tex]S_{1}=1=\frac{1^{2}\cdot 2^{2}}{4}[/tex].
Индукционна стъпка: да допуснем, че [tex]S_{k}=\frac{k^{2}(k+1)^{2}}{4}[/tex] за някое естествено число [tex]k[/tex]. Тогава
[tex]S_{k+1}=S_{k}+(k+1)^{3}=\frac{k^{2}(k+1)^{2}}{4}+(k+1)^{3}=\frac{(k+1)^{2}\left(k^{2}+4k+4\right)}{4}=\frac{(k+1)^{2}(k+2)^{2}}{4}[/tex]
т.е. формулата е вярна и при [tex]n=k+1[/tex]. Съгласно принципа на математическата индукция за всяко естествено [tex]n[/tex]
[tex]1^{3}+2^{3}+\ldots+n^{3}=\left(\frac{n(n+1)}{2}\right)^{2}=\left(1+2+\ldots+n\right)^{2}[/tex]

Решение:
Фиксираме [tex]x\ge -1[/tex] и прилагаме индукция по [tex]n[/tex]. База: при [tex]n=1[/tex] неравенството е [tex]1+x\ge 1+x[/tex], което е вярно (равенство).
Индукционна стъпка: да допуснем, че [tex]\left(1+x\right)^{k}\ge 1+kx[/tex] за някое естествено число [tex]k[/tex]. Тъй като [tex]x\ge -1[/tex], то [tex]1+x\ge 0[/tex] и умножаването на двете страни с [tex]1+x[/tex] запазва посоката на неравенството:
[tex]\left(1+x\right)^{k+1}\ge (1+kx)(1+x)=1+(k+1)x+kx^{2}\ge 1+(k+1)x[/tex]
тъй като [tex]kx^{2}\ge 0[/tex]. Това е неравенството при [tex]n=k+1[/tex], следователно по индукция то е вярно за всяко естествено [tex]n[/tex]. Условието [tex]x\ge -1[/tex] е точно това, което позволява умножаването с [tex]1+x[/tex].

Решение:
Нека [tex]A_{n}=4^{n}+15n-1[/tex]. Прилагаме индукция по [tex]n[/tex]. База: [tex]A_{1}=4+15-1=18=9\cdot 2[/tex] се дели на [tex]9[/tex].
Индукционна стъпка: да допуснем, че [tex]A_{k}[/tex] се дели на [tex]9[/tex] за някое естествено число [tex]k[/tex]. Изразяваме [tex]A_{k+1}[/tex] чрез [tex]A_{k}[/tex]:
[tex]A_{k+1}=4\cdot 4^{k}+15k+14=4\left(4^{k}+15k-1\right)-45k+18=4A_{k}-9(5k-2)[/tex]
Числото [tex]4A_{k}[/tex] се дели на [tex]9[/tex] според индукционното предположение, а [tex]9(5k-2)[/tex] е кратно на [tex]9[/tex], следователно [tex]A_{k+1}[/tex] се дели на [tex]9[/tex]. По индукция [tex]4^{n}+15n-1[/tex] се дели на [tex]9[/tex] за всяко естествено [tex]n[/tex].

Решение:
Пресмятаме първите стойности:
[tex]P_{2}=\frac{3}{4}; \quad P_{3}=\frac{3}{4}\cdot \frac{8}{9}=\frac{2}{3}=\frac{4}{6}; \quad P_{4}=\frac{2}{3}\cdot \frac{15}{16}=\frac{5}{8}[/tex]
Стойностите [tex]\frac{3}{4}[/tex], [tex]\frac{4}{6}[/tex], [tex]\frac{5}{8}[/tex] подсказват, че [tex]P_{n}=\frac{n+1}{2n}[/tex]. Доказваме това по индукция за [tex]n\ge 2[/tex]. База: [tex]P_{2}=\frac{3}{4}=\frac{2+1}{2\cdot 2}[/tex].
Индукционна стъпка: да допуснем, че [tex]P_{k}=\frac{k+1}{2k}[/tex] за някое [tex]k\ge 2[/tex]. Тогава
[tex]P_{k+1}=P_{k}\left(1-\frac{1}{(k+1)^{2}}\right)=\frac{k+1}{2k}\cdot \frac{k(k+2)}{(k+1)^{2}}=\frac{k+2}{2(k+1)}[/tex]
т.е. формулата е вярна и при [tex]n=k+1[/tex]. Следователно [tex]P_{n}=\frac{n+1}{2n}[/tex] за всяко [tex]n\ge 2[/tex].
Формулите [tex]\frac{n+1}{n+2}[/tex] и [tex]\frac{n^{2}-1}{n^{2}}[/tex] дават вярната стойност [tex]P_{2}=\frac{3}{4}[/tex], но грешат още при [tex]n=3[/tex], а [tex]\frac{n+2}{2(n+1)}[/tex] е отместена с един индекс (тя е равна на [tex]P_{n+1}[/tex]).

Решение:
Всеки член се определя от двата предходни, затова проверяваме две начални стойности и допускаме, че формулата е вярна за два последователни индекса. База: при [tex]n=1[/tex] и [tex]n=2[/tex]:
[tex]3\cdot 2^{0}+2\cdot (-1)^{1}=1=a_{1}; \quad 3\cdot 2^{1}+2\cdot (-1)^{2}=8=a_{2}[/tex]
Индукционна стъпка: да допуснем, че за някое [tex]k\ge 3[/tex] формулата е вярна при [tex]n=k-2[/tex] и [tex]n=k-1[/tex]. Като използваме, че [tex](-1)^{k-1}=-(-1)^{k}[/tex] и [tex](-1)^{k-2}=(-1)^{k}[/tex], получаваме
[tex]a_{k}=a_{k-1}+2a_{k-2}=3\cdot 2^{k-2}+2(-1)^{k-1}+2\left(3\cdot 2^{k-3}+2(-1)^{k-2}\right)[/tex]
[tex]=3\cdot 2^{k-2}+3\cdot 2^{k-2}+(-1)^{k}(-2+4)=3\cdot 2^{k-1}+2\cdot (-1)^{k}[/tex]
Следователно формулата е вярна и при [tex]n=k[/tex], и по индукция тя е вярна за всяко естествено [tex]n[/tex].

Решение:
Нека [tex]S_{n}[/tex] е лявата страна; тя се състои от [tex]2n+1[/tex] събираеми от [tex]\frac{1}{n+1}[/tex] до [tex]\frac{1}{3n+1}[/tex]. Прилагаме индукция по [tex]n[/tex]. База:
[tex]S_{1}=\frac{1}{2}+\frac{1}{3}+\frac{1}{4}=\frac{13}{12}\gt 1[/tex]
Индукционна стъпка: да допуснем, че [tex]S_{k}\gt 1[/tex] за някое естествено число [tex]k[/tex]. В сравнение с [tex]S_{k}[/tex] в сбора [tex]S_{k+1}=\frac{1}{k+2}+\ldots+\frac{1}{3k+4}[/tex] отпада събираемото [tex]\frac{1}{k+1}[/tex] и се добавят трите събираеми [tex]\frac{1}{3k+2}[/tex], [tex]\frac{1}{3k+3}[/tex], [tex]\frac{1}{3k+4}[/tex]:
[tex]S_{k+1}=S_{k}+\frac{1}{3k+2}+\frac{1}{3k+3}+\frac{1}{3k+4}-\frac{1}{k+1}[/tex]
Тъй като [tex]\frac{1}{k+1}=\frac{3}{3k+3}[/tex], при [tex]m=3k+3[/tex] получаваме
[tex]S_{k+1}-S_{k}=\frac{1}{m-1}+\frac{1}{m+1}-\frac{2}{m}=\frac{2m}{m^{2}-1}-\frac{2}{m}=\frac{2}{m\left(m^{2}-1\right)}\gt 0[/tex]
тъй като [tex]m\ge 6[/tex]. Следователно [tex]S_{k+1}\gt S_{k}\gt 1[/tex] и по индукция неравенството е вярно за всяко естествено [tex]n[/tex].

Решение:
Прилагаме индукция по [tex]n[/tex] (едновременно за всички [tex]x[/tex]). База: при [tex]n=1[/tex] неравенството е [tex]\left|\sin x\right|\le\left|\sin x\right|[/tex], което е вярно.
Индукционна стъпка: да допуснем, че [tex]\left|\sin kx\right|\le k\left|\sin x\right|[/tex] за някое естествено число [tex]k[/tex] и за всяко реално [tex]x[/tex]. От формулата за синус от сбор
[tex]\sin (k+1)x=\sin kx\cos x+\cos kx\sin x[/tex]
От неравенството на триъгълника, оценките [tex]\left|\cos x\right|\le 1[/tex], [tex]\left|\cos kx\right|\le 1[/tex] и индукционното предположение следва
[tex]\left|\sin (k+1)x\right|\le\left|\sin kx\right|\left|\cos x\right|+\left|\cos kx\right|\left|\sin x\right|\le\left|\sin kx\right|+\left|\sin x\right|[/tex]
[tex]\le k\left|\sin x\right|+\left|\sin x\right|=(k+1)\left|\sin x\right|[/tex]
Това е неравенството при [tex]n=k+1[/tex], следователно по индукция то е вярно за всяко естествено [tex]n[/tex] и всяко реално [tex]x[/tex].

Решение:
Нека [tex]z_{n}=x^{n}+\frac{1}{x^{n}}[/tex]. По условие [tex]z_{1}[/tex] е цяло число, а
[tex]z_{2}=\left(x+\frac{1}{x}\right)^{2}-2=z_{1}^{2}-2[/tex]
също е цяло число. За всяко естествено [tex]n\ge 2[/tex] имаме
[tex]z_{1}z_{n}=\left(x+\frac{1}{x}\right)\left(x^{n}+\frac{1}{x^{n}}\right)=x^{n+1}+\frac{1}{x^{n+1}}+x^{n-1}+\frac{1}{x^{n-1}}=z_{n+1}+z_{n-1}[/tex]
т.е.
[tex]z_{n+1}=z_{1}z_{n}-z_{n-1}[/tex]
Прилагаме индукция с две бази: [tex]z_{1}[/tex] и [tex]z_{2}[/tex] са цели числа. Индукционна стъпка: да допуснем, че [tex]z_{k-1}[/tex] и [tex]z_{k}[/tex] са цели числа за някое [tex]k\ge 2[/tex]. Тогава [tex]z_{k+1}=z_{1}z_{k}-z_{k-1}[/tex] е цяло число като произведение и разлика на цели числа. Следователно [tex]x^{n}+\frac{1}{x^{n}}[/tex] е цяло число за всяко естествено [tex]n[/tex].

Решение:
Нека [tex]R_{n}[/tex] е броят на частите. Една окръжност разделя равнината на [tex]R_{1}=2[/tex] части (вътрешност и външност). Да допуснем, че са начертани [tex]k\ge 1[/tex] окръжности, и добавяме [tex](k+1)[/tex]-вата. Тя пресича всяка от старите [tex]k[/tex] окръжности в точно две точки и тези [tex]2k[/tex] точки са различни, защото никои три окръжности не минават през една точка. Те разделят новата окръжност на [tex]2k[/tex] дъги.
Никоя дъга не съдържа пресечни точки във вътрешността си, затова всяка дъга лежи в една от съществуващите части и я разделя на две. Следователно всяка дъга добавя точно една част:
[tex]R_{k+1}=R_{k}+2k[/tex]
Оттук получаваме
[tex]R_{1}=2; \quad R_{2}=4; \quad R_{3}=8; \quad R_{4}=14[/tex]
и доказваме, че [tex]R_{n}=n^{2}-n+2[/tex], по индукция. База: [tex]R_{1}=1-1+2=2[/tex]. Индукционна стъпка: ако [tex]R_{k}=k^{2}-k+2[/tex] за някое естествено [tex]k[/tex], то
[tex]R_{k+1}=k^{2}-k+2+2k=k^{2}+k+2=(k+1)^{2}-(k+1)+2[/tex]
Следователно окръжностите разделят равнината на [tex]n^{2}-n+2[/tex] части. Забележете, че [tex]2^{n}[/tex] съвпада с първите три стойности, но при [tex]n=4[/tex] дава [tex]16[/tex] вместо [tex]14[/tex], затова отгатнатата закономерност винаги трябва да се доказва.

Решение:
Проверяваме малките стойности. При [tex]n=1[/tex] неравенството [tex]2\gt 1[/tex] е вярно, но при [tex]2\le n\le 9[/tex] не е изпълнено, защото стойностите на [tex]2^{n}[/tex] и [tex]n^{3}[/tex] са
[tex]4\lt 8; \quad 8\lt 27; \quad 16\lt 64; \quad 32\lt 125; \quad 64\lt 216; \quad 128\lt 343; \quad 256\lt 512; \quad 512\lt 729[/tex]
Тъй като неравенството не е изпълнено при [tex]n=9[/tex], трябва [tex]n_{0}\ge 10[/tex]. Доказваме по индукция, че то е вярно за всяко [tex]n\ge 10[/tex]. База:
[tex]2^{10}=1024\gt 1000=10^{3}[/tex]
Индукционна стъпка: да допуснем, че [tex]2^{k}\gt k^{3}[/tex] за някое [tex]k\ge 10[/tex]. Тогава, тъй като [tex]k\ge 10[/tex],
[tex]2^{k+1}=2\cdot 2^{k}\gt 2k^{3}=k^{3}+k\cdot k^{2}\ge k^{3}+10k^{2}[/tex]
Освен това [tex]3k^{2}\ge 3k[/tex] и [tex]4k^{2}\ge 1[/tex], затова
[tex]10k^{2}=3k^{2}+3k^{2}+4k^{2}\ge 3k^{2}+3k+1[/tex]
Следователно
[tex]2^{k+1}\gt k^{3}+3k^{2}+3k+1=(k+1)^{3}[/tex]
И така, неравенството е вярно за всяко [tex]n\ge 10[/tex] и най-малкото такова число е [tex]n_{0}=10[/tex].

Решение:
Сума от [tex]k[/tex] евроцента може да се плати точно когато [tex]k=5x+7y[/tex] с цели неотрицателни числа [tex]x[/tex] и [tex]y[/tex]. Сумата [tex]23[/tex] не може да се плати: тъй като [tex]7y\le 23[/tex], имаме [tex]y\in\left\{0; 1; 2; 3\right\}[/tex], а
[tex]23-7y\in\left\{23; 16; 9; 2\right\}[/tex]
и никое от тези числа не се дели на [tex]5[/tex]. Следователно [tex]Z\ge 24[/tex]. Доказваме по индукция, че всяка сума [tex]k\ge 24[/tex] може да се плати. База:
[tex]24=2\cdot 5+2\cdot 7[/tex]
Индукционна стъпка: да допуснем, че [tex]k=5x+7y[/tex] с цели [tex]x,y\ge 0[/tex] за някое [tex]k\ge 24[/tex]. Ако [tex]y\ge 2[/tex], заменяме две марки от [tex]7[/tex] евроцента ([tex]14[/tex] евроцента) с три марки от [tex]5[/tex] евроцента ([tex]15[/tex] евроцента):
[tex]k+1=5(x+3)+7(y-2)[/tex]
Ако [tex]y\le 1[/tex], то [tex]5x=k-7y\ge 24-7=17[/tex], следователно [tex]x\ge 4[/tex]; заменяме четири марки от [tex]5[/tex] евроцента ([tex]20[/tex] евроцента) с три марки от [tex]7[/tex] евроцента ([tex]21[/tex] евроцента):
[tex]k+1=5(x-4)+7(y+3)[/tex]
И в двата случая [tex]k+1[/tex] може да се плати. Следователно всяка сума [tex]k\ge 24[/tex] може да се плати, а [tex]23[/tex] не може, т.е. [tex]Z=24[/tex].

Решение:
Нека
[tex]P_{n}=\frac{1}{2}\cdot \frac{3}{4}\cdot \ldots\cdot \frac{2n-1}{2n}[/tex]
Директната индукция не работи: от [tex]P_{k}\lt\frac{1}{\sqrt{3k-1}}[/tex] би трябвало да следва
[tex]\frac{2k+1}{(2k+2)\sqrt{3k-1}}\le\frac{1}{\sqrt{3k+2}}\iff(2k+1)^{2}(3k+2)\le(2k+2)^{2}(3k-1)[/tex]
[tex]\iff 12k^{3}+20k^{2}+11k+2\le 12k^{3}+20k^{2}+4k-4[/tex]
което е невярно. Затова доказваме по-силното твърдение
[tex]P_{n}\le\frac{1}{\sqrt{3n+1}}\qquad(*)[/tex]
за всяко естествено [tex]n[/tex]; по-силното индукционно предположение прави стъпката възможна. База: [tex]P_{1}=\frac{1}{2}=\frac{1}{\sqrt{4}}[/tex].
Индукционна стъпка: да допуснем, че [tex]P_{k}\le\frac{1}{\sqrt{3k+1}}[/tex] за някое естествено [tex]k[/tex]. Тогава
[tex]P_{k+1}=P_{k}\cdot \frac{2k+1}{2k+2}\le\frac{2k+1}{(2k+2)\sqrt{3k+1}}[/tex]
Достатъчно е да покажем, че дясната страна не надминава [tex]\frac{1}{\sqrt{3k+4}}[/tex]. Двете страни са положителни, затова това е еквивалентно на неравенството между квадратите им:
[tex]\frac{2k+1}{(2k+2)\sqrt{3k+1}}\le\frac{1}{\sqrt{3k+4}}\iff(2k+1)^{2}(3k+4)\le(2k+2)^{2}(3k+1)[/tex]
[tex]\iff 12k^{3}+28k^{2}+19k+4\le 12k^{3}+28k^{2}+20k+4\iff 0\le k[/tex]
което е вярно. Следователно [tex]P_{k+1}\le\frac{1}{\sqrt{3k+4}}=\frac{1}{\sqrt{3(k+1)+1}}[/tex] и (*) е вярно за всяко естествено [tex]n[/tex]. Накрая, при [tex]n\gt 1[/tex] имаме [tex]3n+1\gt 3n-1\gt 0[/tex], затова
[tex]P_{n}\le\frac{1}{\sqrt{3n+1}}\lt\frac{1}{\sqrt{3n-1}}[/tex]

Решение:
Нека [tex]A_{n}=82^{n+1}+(45n-82)\cdot 127^{n}[/tex] и да отбележим, че [tex]127-82=45[/tex]. Прилагаме индукция по [tex]n[/tex]. База:
[tex]A_{1}=82^{2}+(45-82)\cdot 127=6724-4699=2025=45^{2}[/tex]
За да свържем [tex]A_{k+1}[/tex] с [tex]A_{k}[/tex], пресмятаме (като използваме, че [tex]45(k+1)-82=45k-37[/tex])
[tex]A_{k+1}-82A_{k}=82^{k+2}+(45k-37)\cdot 127^{k+1}-82^{k+2}-82(45k-82)\cdot 127^{k}[/tex]
[tex]=127^{k}\left[127(45k-37)-82(45k-82)\right][/tex]
Изразът в скобите е равен на
[tex]45k(127-82)-127\cdot 37+82^{2}=45^{2}k-4699+6724=2025k+2025=45^{2}(k+1)[/tex]
Следователно
[tex]A_{k+1}=82A_{k}+45^{2}(k+1)\cdot 127^{k}[/tex]
Индукционна стъпка: да допуснем, че [tex]A_{k}[/tex] се дели на [tex]45^{2}[/tex] за някое естествено [tex]k[/tex]. Тогава и двете събираеми вдясно се делят на [tex]45^{2}[/tex], следователно [tex]A_{k+1}[/tex] се дели на [tex]45^{2}[/tex]. По индукция [tex]A_{n}[/tex] се дели на [tex]45^{2}[/tex] за всяко естествено [tex]n[/tex].

Решение:
Доказваме по индукция по [tex]n[/tex], че червената част може да бъде покрита при всяко положение на синьото квадратче. База: при [tex]n=1[/tex] квадратът има страна [tex]2[/tex] и червената му част се състои от три единични квадратчета, които образуват точно едно Г-тримино.
Индукционна стъпка: да допуснем, че за някое естествено [tex]k[/tex] всеки квадрат със страна [tex]2^{k}[/tex] с едно произволно изключено единично квадратче може да бъде покрит с Г-тримина. Разделяме квадрат със страна [tex]2^{k+1}[/tex] с отсечките, свързващи средите на срещуположните му страни, на четири квадранта — квадрати със страна [tex]2^{k}[/tex]. Синьото квадратче лежи в точно един квадрант.
Всеки от другите три квадранта има ъглово единично квадратче в центъра на големия квадрат; тези три квадратчета образуват Г-тримино и поставяме едно тримино върху тях. Сега всеки от четирите квадранта е квадрат със страна [tex]2^{k}[/tex] с точно едно изключено единично квадратче (синьото или покритото от централното тримино).
Според индукционното предположение всеки квадрант може да бъде покрит и заедно с централното тримино това покрива цялата червена част. Следователно твърдението е вярно за всяко естествено [tex]n[/tex]. Това е в съгласие с броя на червените квадратчета: [tex]4^{n}-1[/tex] се дели на [tex]3[/tex].