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

Решение:
Так как [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].