bulgakov

Математическая индукция: равенства, делимость и неравенства

Семинар 09.09.2026. Метод математической индукции: суммы, делимость и неравенства. Задачи №18–21 из §2 задачника Карапетяна, печатная страница 12.

Проверить формулу при двух или трёх значениях nn полезно, но этого недостаточно для доказательства. Индукция позволяет обосновать сразу бесконечно много случаев: мы проверяем первый и показываем, как из любого уже верного случая получить следующий.

Как устроено доказательство по индукции

Пусть утверждение зависит от натурального числа nn. Здесь N={1,2,3,…}\mathbb N=\{1,2,3,\ldots\}. Доказательство состоит из двух частей.

  1. База. Проверяем самое первое допустимое значение nn. Обычно это n=1n=1, но в некоторых задачах удобнее или необходимо начать с n=2n=2 либо n=3n=3. Если меньшие номера тоже входят в условие, их проверяем отдельно.
  2. Переход. Берём произвольное допустимое число kk. Предполагаем, что утверждение верно при n=kn=k, и с помощью этого предположения доказываем его при n=k+1n=k+1.

Тогда база даёт первый случай, переход — второй, затем третий и так далее. Поэтому утверждение верно для всех натуральных чисел, начиная с проверенной базы.

Буква kk обозначает не какое-то специально выбранное число, а любой номер, для которого мы выполняем один и тот же переход. В предположении мы временно используем только случай n=kn=k. Случай n=k+1n=k+1 ещё предстоит получить.

В каждом решении полезно сначала отдельно выписать цель перехода: заменить nn на k+1k+1 в исходной формуле. Так будет видно, к какому выражению нужно прийти. Сама запись цели ничего не доказывает; доказательством станет цепочка преобразований, которая к ней приведёт.

Классная работа: формулы для сумм

№18(1). Сумма первых натуральных чисел

Доказать при каждом n∈Nn\in\mathbb N:

1+2+⋯+n=n(n+1)2.1+2+\cdots+n=\frac{n(n+1)}{2}.

База n=1n=1. Слева стоит 11, справа — 1⋅22=1\frac{1\cdot2}{2}=1. Равенство верно.

Предположение. Пусть для некоторого k≥1k\ge1 уже верно

1+2+⋯+k=k(k+1)2.1+2+\cdots+k=\frac{k(k+1)}{2}.

Цель. Для следующего числа нужно получить

1+2+⋯+k+(k+1)=(k+1)(k+2)2.1+2+\cdots+k+(k+1) =\frac{(k+1)(k+2)}{2}.

Сумма стала длиннее ровно на одно слагаемое — k+1k+1. Её прежнюю часть заменяем по предположению:

1+2+⋯+k+(k+1)=k(k+1)2+(k+1)=(k+1)(k2+1)=(k+1)(k+2)2.\begin{aligned} 1+2+\cdots+k+(k+1) &=\frac{k(k+1)}{2}+(k+1)\\ &=(k+1)\left(\frac{k}{2}+1\right)\\ &=\frac{(k+1)(k+2)}{2}. \end{aligned}

Получилась именно цель. База и переход доказаны, значит, формула верна для всех n≥1n\ge1.

Здесь виден основной приём для сумм: сумма до следующего номера = прежняя сумма + новое слагаемое.

№18(2). Сумма квадратов

Доказать при каждом n∈Nn\in\mathbb N:

12+22+⋯+n2=n(n+1)(2n+1)6.1^2+2^2+\cdots+n^2 =\frac{n(n+1)(2n+1)}{6}.

База n=1n=1. Обе стороны равны 11, поскольку 1⋅2⋅36=1\frac{1\cdot2\cdot3}{6}=1.

Предположение:

12+22+⋯+k2=k(k+1)(2k+1)6.1^2+2^2+\cdots+k^2 =\frac{k(k+1)(2k+1)}{6}.

Цель при n=k+1n=k+1:

12+⋯+k2+(k+1)2=(k+1)(k+2)(2k+3)6.1^2+\cdots+k^2+(k+1)^2 =\frac{(k+1)(k+2)(2k+3)}{6}.

Обратите внимание на последний множитель: 2(k+1)+1=2k+32(k+1)+1=2k+3. Теперь добавляем новый квадрат:

12+⋯+k2+(k+1)2=k(k+1)(2k+1)6+(k+1)2=(k+1)(k(2k+1)+6(k+1))6=(k+1)(2k2+7k+6)6.\begin{aligned} 1^2+\cdots+k^2+(k+1)^2 &=\frac{k(k+1)(2k+1)}{6}+(k+1)^2\\ &=\frac{(k+1)\bigl(k(2k+1)+6(k+1)\bigr)}{6}\\ &=\frac{(k+1)(2k^2+7k+6)}{6}. \end{aligned}

Чтобы получить цель, осталось разложить трёхчлен. Разбиваем 7k7k на 4k+3k4k+3k и группируем:

2k2+7k+6=2k2+4k+3k+6=2k(k+2)+3(k+2)=(k+2)(2k+3).\begin{aligned} 2k^2+7k+6 &=2k^2+4k+3k+6\\ &=2k(k+2)+3(k+2)\\ &=(k+2)(2k+3). \end{aligned}

Следовательно,

12+⋯+k2+(k+1)2=(k+1)(k+2)(2k+3)6.1^2+\cdots+k^2+(k+1)^2 =\frac{(k+1)(k+2)(2k+3)}{6}.

Переход выполнен, формула доказана.

№18(3). Сумма кубов

Доказать при каждом n∈Nn\in\mathbb N:

13+23+⋯+n3=(1+2+⋯+n)2.1^3+2^3+\cdots+n^3=(1+2+\cdots+n)^2.

По уже доказанному пункту №18(1) правая часть равна (n(n+1)2)2\left(\frac{n(n+1)}{2}\right)^2. Поэтому докажем равносильную формулу

13+23+⋯+n3=(n(n+1)2)2.1^3+2^3+\cdots+n^3 =\left(\frac{n(n+1)}{2}\right)^2.

База n=1n=1. Получаем 1=11=1.

Предположение:

13+⋯+k3=(k(k+1)2)2.1^3+\cdots+k^3 =\left(\frac{k(k+1)}{2}\right)^2.

Цель. После добавления (k+1)3(k+1)^3 должна получиться величина ((k+1)(k+2)2)2\left(\frac{(k+1)(k+2)}{2}\right)^2.

Используем предположение и выносим общий множитель (k+1)2(k+1)^2:

13+⋯+k3+(k+1)3=k2(k+1)24+(k+1)3=(k+1)2(k24+k+1)=(k+1)2(k2+4k+4)4=(k+1)2(k+2)24=((k+1)(k+2)2)2.\begin{aligned} 1^3+\cdots+k^3+(k+1)^3 &=\frac{k^2(k+1)^2}{4}+(k+1)^3\\ &=(k+1)^2\left(\frac{k^2}{4}+k+1\right)\\ &=\frac{(k+1)^2(k^2+4k+4)}{4}\\ &=\frac{(k+1)^2(k+2)^2}{4}\\ &=\left(\frac{(k+1)(k+2)}{2}\right)^2. \end{aligned}

В предпоследнем переходе использован квадрат суммы: k2+4k+4=(k+2)2k^2+4k+4=(k+2)^2. Цель получена. Значит, сумма первых nn кубов действительно равна квадрату суммы первых nn натуральных чисел.

№18(5). Сумма произведений

Доказать при каждом n∈Nn\in\mathbb N:

1⋅2+2⋅5+⋯+n(3n−1)=n2(n+1).1\cdot2+2\cdot5+\cdots+n(3n-1)=n^2(n+1).

Здесь слагаемое с номером nn имеет вид n(3n−1)n(3n-1). Например, третье слагаемое равно 3⋅83\cdot8. Чтобы продолжить сумму, нужно увеличить номер в обоих местах.

База n=1n=1:

1⋅2=12(1+1)=2.1\cdot2=1^2(1+1)=2.

Предположение:

1⋅2+2⋅5+⋯+k(3k−1)=k2(k+1).1\cdot2+2\cdot5+\cdots+k(3k-1)=k^2(k+1).

Цель при n=k+1n=k+1:

1⋅2+⋯+k(3k−1)+(k+1)(3k+2)=(k+1)2(k+2).1\cdot2+\cdots+k(3k-1)+(k+1)(3k+2) =(k+1)^2(k+2).

Новое слагаемое получилось так:

(k+1)(3(k+1)−1)=(k+1)(3k+2).(k+1)\bigl(3(k+1)-1\bigr)=(k+1)(3k+2).

Подставляем прежнюю сумму и выносим (k+1)(k+1):

1⋅2+⋯+k(3k−1)+(k+1)(3k+2)=k2(k+1)+(k+1)(3k+2)=(k+1)(k2+3k+2)=(k+1)(k+1)(k+2)=(k+1)2(k+2).\begin{aligned} 1\cdot2+\cdots+k(3k-1)+(k+1)(3k+2) &=k^2(k+1)+(k+1)(3k+2)\\ &=(k+1)(k^2+3k+2)\\ &=(k+1)(k+1)(k+2)\\ &=(k+1)^2(k+2). \end{aligned}

Разложение k2+3k+2=(k+1)(k+2)k^2+3k+2=(k+1)(k+2) даёт нужный результат. Формула доказана.

Классная работа: делимость

№19(1). Выделяем выражение из предположения

Доказать: при каждом n∈Nn\in\mathbb N число

5⋅23n−2+33n−15\cdot2^{3n-2}+3^{3n-1}

кратно 1919.

«Кратно 1919» означает «равно 19m19m для некоторого целого числа mm». Сумма двух чисел, кратных 1919, тоже кратна 1919; умножение на целое число также сохраняет делимость. На этих свойствах и построим переход.

База n=1n=1:

5⋅23⋅1−2+33⋅1−1=5⋅2+32=19.5\cdot2^{3\cdot1-2}+3^{3\cdot1-1} =5\cdot2+3^2=19.

Предположение. Число

Ak=5⋅23k−2+33k−1A_k=5\cdot2^{3k-2}+3^{3k-1}

делится на 1919. Обозначение AkA_k введено только для удобства: так короче ссылаться на всё выражение.

Цель. Доказать делимость следующего числа:

Ak+1=5⋅23k+1+33k+2.A_{k+1}=5\cdot2^{3k+1}+3^{3k+2}.

Почему показатели именно такие? При подстановке k+1k+1 получаем 3(k+1)−2=3k+13(k+1)-2=3k+1 и 3(k+1)−1=3k+23(k+1)-1=3k+2.

По сравнению с AkA_k степень двойки умножилась на 23=82^3=8, а степень тройки — на 33=273^3=27. Выделим восемь копий прежнего выражения. Для этого из 2727 копий степени тройки восемь отправим в скобку, а остальные 27−8=1927-8=19 оставим снаружи:

Ak+1=8⋅5⋅23k−2+27⋅33k−1=8(5⋅23k−2+33k−1)+(27−8)33k−1=8Ak+19⋅33k−1.\begin{aligned} A_{k+1} &=8\cdot5\cdot2^{3k-2}+27\cdot3^{3k-1}\\ &=8\left(5\cdot2^{3k-2}+3^{3k-1}\right) +(27-8)3^{3k-1}\\ &=8A_k+19\cdot3^{3k-1}. \end{aligned}

Первое слагаемое делится на 1919 по предположению, второе — из-за явного множителя 1919. Поэтому делится и Ak+1A_{k+1}. Вместе с базой это доказывает утверждение для всех n≥1n\ge1.

Классная работа: неравенство Бернулли

№20. Произведение разных множителей

Условие. Числа x1,x2,…,xnx_1,x_2,\ldots,x_n одного и того же знака, причём каждое из них больше −1-1. Доказать:

(1+x1)(1+x2)⋯(1+xn)≥1+x1+x2+⋯+xn.(1+x_1)(1+x_2)\cdots(1+x_n) \ge1+x_1+x_2+\cdots+x_n.

В этой задаче индекс обозначает номер числа: x1x_1 — первое число, x2x_2 — второе, а nn — количество множителей. При увеличении nn мы добавляем ещё один множитель.

Обе предпосылки нужны в доказательстве. Из xi>−1x_i>-1 следует 1+xi>01+x_i>0, поэтому на такой множитель можно умножать неравенство, сохраняя его знак. Общий знак чисел позволит отбросить дополнительное неотрицательное слагаемое.

При n=1n=1 имеем равенство 1+x1=1+x11+x_1=1+x_1. Первый содержательный случай, с которого начинается разбор в тетради, — n=2n=2:

(1+x1)(1+x2)=1+x1+x2+x1x2≥1+x1+x2.(1+x_1)(1+x_2) =1+x_1+x_2+x_1x_2 \ge1+x_1+x_2.

Последний переход верен, потому что у x1x_1 и x2x_2 одинаковый знак, а значит, x1x2≥0x_1x_2\ge0.

Предположение. Для kk таких чисел уже доказано

(1+x1)⋯(1+xk)≥1+x1+⋯+xk.(1+x_1)\cdots(1+x_k) \ge1+x_1+\cdots+x_k.

Цель. Получить неравенство для k+1k+1 множителей с правой частью 1+x1+⋯+xk+xk+11+x_1+\cdots+x_k+x_{k+1}.

Умножаем предположение на положительное число 1+xk+11+x_{k+1}:

(1+x1)⋯(1+xk)(1+xk+1)≥(1+x1+⋯+xk)(1+xk+1)=1+x1+⋯+xk+xk+1+xk+1(x1+⋯+xk).\begin{aligned} (1+x_1)\cdots(1+x_k)(1+x_{k+1}) &\ge(1+x_1+\cdots+x_k)(1+x_{k+1})\\ &=1+x_1+\cdots+x_k+x_{k+1}\\ &\quad+x_{k+1}(x_1+\cdots+x_k). \end{aligned}

Разберём знак последнего слагаемого. Если все xix_i положительны, положительны и xk+1x_{k+1}, и сумма в скобках. Если все отрицательны, оба множителя отрицательны. В любом случае

xk+1(x1+⋯+xk)≥0.x_{k+1}(x_1+\cdots+x_k)\ge0.

Отбросив это неотрицательное слагаемое, получаем

(1+x1)⋯(1+xk+1)≥1+x1+⋯+xk+1.(1+x_1)\cdots(1+x_{k+1}) \ge1+x_1+\cdots+x_{k+1}.

Переход доказан. Если среди чисел есть нули, рассуждение также работает: достаточно, чтобы все числа были неотрицательны либо все неположительны и по-прежнему больше −1-1.

Что переносится из одной задачи в другую

У индукции одна схема, но разные способы выполнить переход:

  • Суммы: отделить новое слагаемое и заменить прежнюю сумму по предположению.
  • Делимость: представить следующее выражение через предыдущее и добавку, которая явно делится на нужное число.
  • Неравенства: применить предположение и проверить, что последующие действия сохраняют знак. При умножении важно знать знак множителя.

Перед длинными вычислениями выпишите цель при n=k+1n=k+1. Частая ошибка — заменить номер только в одном месте, забыв про остальные множители, показатели или границы суммы.

Самостоятельная практика по тетради

По домашнему блоку в тетради: №18(4, 6, 7, 8), №19(2, 3, 4), №21, печатная страница 12. На полях также записаны №18(4–8) и №20; №18(5) и №20 уже разобраны выше на занятии. Их решения можно использовать как образцы для самостоятельной работы.

Во всех пунктах №18 и №19 утверждение требуется доказать для каждого n∈Nn\in\mathbb N. В №18(7) и №18(8) первая непустая сумма получается при n=2n=2: с неё удобно начать индукцию. При n=1n=1 обе стороны равны нулю, если сумму без слагаемых считать равной нулю.

№18. Доказать равенства по индукции

Пункт 4:

1+2+22+⋯+2n−1=2n−1.1+2+2^2+\cdots+2^{n-1}=2^n-1.

Пункт 6:

12+32+⋯+(2n−1)2=n(4n2−1)3.1^2+3^2+\cdots+(2n-1)^2 =\frac{n(4n^2-1)}{3}.

Пункт 7:

1⋅2+2⋅3+3⋅4+⋯+(n−1)n=(n−1)n(n+1)3.1\cdot2+2\cdot3+3\cdot4+\cdots+(n-1)n =\frac{(n-1)n(n+1)}{3}.

Пункт 8:

1⋅22+2⋅32+⋯+(n−1)n2=n(n2−1)(3n+2)12.1\cdot2^2+2\cdot3^2+\cdots+(n-1)n^2 =\frac{n(n^2-1)(3n+2)}{12}.

№19. Доказать делимость по индукции

  • Пункт 2: число n(2n2−3n+1)n(2n^2-3n+1) кратно 66.
  • Пункт 3: число 62n−2+3n+1+3n−16^{2n-2}+3^{n+1}+3^{n-1} кратно 1111.
  • Пункт 4: число n5−nn^5-n кратно 55.

№21. Доказать неравенство Бернулли

Для любого n∈Nn\in\mathbb N и любого действительного x>−1x>-1 доказать:

(1+x)n≥1+nx.(1+x)^n\ge1+nx.

Сначала попробуйте в каждом пункте самостоятельно записать базу, предположение и цель. Полные решения находятся в закрытом разборе ниже.

Разбор самостоятельных задач

№18(4). Сумма степеней двойки

Сумма содержит nn слагаемых. Последний показатель равен n−1n-1, поэтому при переходе к n=k+1n=k+1 добавляется 2k2^k.

База n=1n=1: слева только 11, справа 21−1=12^1-1=1.

Предположение:

1+2+⋯+2k−1=2k−1.1+2+\cdots+2^{k-1}=2^k-1.

Цель: доказать, что сумма до 2k2^k равна 2k+1−12^{k+1}-1.

Добавляем следующее слагаемое и используем предположение:

1+2+⋯+2k−1+2k=(2k−1)+2k=2⋅2k−1=2k+1−1.\begin{aligned} 1+2+\cdots+2^{k-1}+2^k &=(2^k-1)+2^k\\ &=2\cdot2^k-1\\ &=2^{k+1}-1. \end{aligned}

Получена цель. Значит, равенство верно для всех n≥1n\ge1.

№18(6). Сумма квадратов нечётных чисел

База n=1n=1:

12=1⋅(4⋅12−1)3=1.1^2=\frac{1\cdot(4\cdot1^2-1)}{3}=1.

Предположение:

12+32+⋯+(2k−1)2=k(4k2−1)3.1^2+3^2+\cdots+(2k-1)^2 =\frac{k(4k^2-1)}{3}.

Цель при n=k+1n=k+1:

12+32+⋯+(2k+1)2=(k+1)(4(k+1)2−1)3.1^2+3^2+\cdots+(2k+1)^2 =\frac{(k+1)\bigl(4(k+1)^2-1\bigr)}{3}.

Следующее нечётное число — 2(k+1)−1=2k+12(k+1)-1=2k+1. Поэтому к прежней сумме прибавляем (2k+1)2(2k+1)^2:

k(4k2−1)3+(2k+1)2=4k3−k+3(4k2+4k+1)3=4k3+12k2+11k+33.\begin{aligned} \frac{k(4k^2-1)}{3}+(2k+1)^2 &=\frac{4k^3-k+3(4k^2+4k+1)}{3}\\ &=\frac{4k^3+12k^2+11k+3}{3}. \end{aligned}

Теперь отдельно раскроем скобки в цели и проверим совпадение:

(k+1)(4(k+1)2−1)3=(k+1)(4k2+8k+3)3=4k3+12k2+11k+33.\begin{aligned} \frac{(k+1)\bigl(4(k+1)^2-1\bigr)}{3} &=\frac{(k+1)(4k^2+8k+3)}{3}\\ &=\frac{4k^3+12k^2+11k+3}{3}. \end{aligned}

Обе стороны равны одному выражению. Следовательно, переход выполнен и формула доказана. Здесь не обязательно угадывать разложение многочлена: достаточно аккуратно раскрыть скобки в обеих сравниваемых частях.

№18(7). Сумма произведений соседних чисел

В этой сумме nn обозначает второе число в последнем произведении, а количество слагаемых равно n−1n-1. Поэтому при увеличении nn на единицу новое слагаемое — k(k+1)k(k+1).

База n=2n=2:

1⋅2=(2−1)⋅2⋅(2+1)3=2.1\cdot2=\frac{(2-1)\cdot2\cdot(2+1)}{3}=2.

Предположение для k≥2k\ge2:

1⋅2+⋯+(k−1)k=(k−1)k(k+1)3.1\cdot2+\cdots+(k-1)k =\frac{(k-1)k(k+1)}{3}.

Цель: получить сумму до k(k+1)k(k+1), равную k(k+1)(k+2)3\frac{k(k+1)(k+2)}{3}.

Прибавляем новое слагаемое:

1⋅2+⋯+(k−1)k+k(k+1)=(k−1)k(k+1)3+k(k+1)=k(k+1)(k−13+1)=k(k+1)(k+2)3.\begin{aligned} 1\cdot2+\cdots+(k-1)k+k(k+1) &=\frac{(k-1)k(k+1)}{3}+k(k+1)\\ &=k(k+1)\left(\frac{k-1}{3}+1\right)\\ &=\frac{k(k+1)(k+2)}{3}. \end{aligned}

Получили цель, значит, формула верна для всех n≥2n\ge2. При n=1n=1 сумма пустая и равна 00, правая часть также равна 00. Этот случай тоже учтён.

№18(8). Следим за последним слагаемым

Здесь последний член равен (n−1)n2(n-1)n^2. После замены nn на k+1k+1 он становится k(k+1)2k(k+1)^2. К прежней сумме нужно добавить именно его, а не (k+1)(k+2)2(k+1)(k+2)^2.

База n=2n=2:

1⋅22=4,2(22−1)(3⋅2+2)12=2⋅3⋅812=4.1\cdot2^2=4, \qquad \frac{2(2^2-1)(3\cdot2+2)}{12} =\frac{2\cdot3\cdot8}{12}=4.

Предположение для k≥2k\ge2:

1⋅22+⋯+(k−1)k2=k(k2−1)(3k+2)12.1\cdot2^2+\cdots+(k-1)k^2 =\frac{k(k^2-1)(3k+2)}{12}.

Цель. Правая часть при n=k+1n=k+1 должна быть равна

(k+1)((k+1)2−1)(3(k+1)+2)12=(k+1)k(k+2)(3k+5)12,\begin{aligned} \frac{(k+1)\bigl((k+1)^2-1\bigr)\bigl(3(k+1)+2\bigr)}{12} &=\frac{(k+1)k(k+2)(3k+5)}{12}, \end{aligned}

поскольку (k+1)2−1=k(k+2)(k+1)^2-1=k(k+2) и 3(k+1)+2=3k+53(k+1)+2=3k+5.

Прибавляем к прежней сумме k(k+1)2k(k+1)^2. В первом слагаемом используем k2−1=(k−1)(k+1)k^2-1=(k-1)(k+1), а второе приводим к знаменателю 1212:

k(k2−1)(3k+2)12+k(k+1)2=k(k+1)(k−1)(3k+2)+12k(k+1)212=k(k+1)((k−1)(3k+2)+12(k+1))12.\begin{aligned} \frac{k(k^2-1)(3k+2)}{12}+k(k+1)^2 &=\frac{k(k+1)(k-1)(3k+2)+12k(k+1)^2}{12}\\ &=\frac{k(k+1)\bigl((k-1)(3k+2)+12(k+1)\bigr)}{12}. \end{aligned}

Разберём оставшуюся скобку:

(k−1)(3k+2)+12(k+1)=3k2−k−2+12k+12=3k2+11k+10=(k+2)(3k+5).\begin{aligned} (k-1)(3k+2)+12(k+1) &=3k^2-k-2+12k+12\\ &=3k^2+11k+10\\ &=(k+2)(3k+5). \end{aligned}

Последнее разложение легко проверить обратным умножением: (k+2)(3k+5)=3k2+5k+6k+10(k+2)(3k+5)=3k^2+5k+6k+10.

Значит, новая сумма равна

k(k+1)(k+2)(3k+5)12.\frac{k(k+1)(k+2)(3k+5)}{12}.

Это и есть цель. Формула доказана для n≥2n\ge2, а при n=1n=1 обе стороны равны нулю при соглашении о пустой сумме. На следующем занятии этот пункт ещё раз разбирается в классе.

№19(2). Разность соседних выражений

Требуется доказать, что n(2n2−3n+1)n(2n^2-3n+1) делится на 66. Сначала разложим квадратный трёхчлен:

2n2−3n+1=(n−1)(2n−1).2n^2-3n+1=(n-1)(2n-1).

Поэтому будем работать с выражением

An=n(n−1)(2n−1).A_n=n(n-1)(2n-1).

База n=1n=1: A1=0A_1=0. Ноль делится на 66, потому что 0=6⋅00=6\cdot0.

Предположение. Число Ak=k(k−1)(2k−1)A_k=k(k-1)(2k-1) делится на 66.

Цель. Доказать делимость Ak+1=(k+1)k(2k+1)A_{k+1}=(k+1)k(2k+1).

Вычислим, насколько следующее выражение отличается от предыдущего:

Ak+1−Ak=k(k+1)(2k+1)−k(k−1)(2k−1)=k((k+1)(2k+1)−(k−1)(2k−1))=k((2k2+3k+1)−(2k2−3k+1))=6k2.\begin{aligned} A_{k+1}-A_k &=k(k+1)(2k+1)-k(k-1)(2k-1)\\ &=k\bigl((k+1)(2k+1)-(k-1)(2k-1)\bigr)\\ &=k\bigl((2k^2+3k+1)-(2k^2-3k+1)\bigr)\\ &=6k^2. \end{aligned}

Таким образом, Ak+1=Ak+6k2A_{k+1}=A_k+6k^2. Первое слагаемое кратно 66 по предположению, второе — очевидно кратно 66. Поэтому кратно и следующее выражение. Утверждение доказано.

№19(3). Приводим степени к удобному виду

Нужно доказать делимость на 1111 числа

62n−2+3n+1+3n−1.6^{2n-2}+3^{n+1}+3^{n-1}.

Во всех степенях удобно выделить показатель n−1n-1:

62n−2=62(n−1)=36n−1,6^{2n-2}=6^{2(n-1)}=36^{n-1}, 3n+1+3n−1=32⋅3n−1+3n−1=10⋅3n−1.3^{n+1}+3^{n-1} =3^2\cdot3^{n-1}+3^{n-1} =10\cdot3^{n-1}.

Исходное выражение равно An=36n−1+10⋅3n−1A_n=36^{n-1}+10\cdot3^{n-1}.

База n=1n=1: A1=360+10⋅30=1+10=11A_1=36^0+10\cdot3^0=1+10=11.

Предположение. Пусть

36k−1+10⋅3k−1=11m,m∈Z.36^{k-1}+10\cdot3^{k-1}=11m, \qquad m\in\mathbb Z.

Здесь mm — целое частное от деления AkA_k на 1111. Выразим из предположения первую степень:

36k−1=11m−10⋅3k−1.36^{k-1}=11m-10\cdot3^{k-1}.

Цель. Показать, что Ak+1=36k+10⋅3kA_{k+1}=36^k+10\cdot3^k также имеет целый множитель при 1111.

Подставляем найденное выражение:

Ak+1=36⋅36k−1+30⋅3k−1=36(11m−10⋅3k−1)+30⋅3k−1=396m−360⋅3k−1+30⋅3k−1=396m−330⋅3k−1=11(36m−30⋅3k−1).\begin{aligned} A_{k+1} &=36\cdot36^{k-1}+30\cdot3^{k-1}\\ &=36\bigl(11m-10\cdot3^{k-1}\bigr)+30\cdot3^{k-1}\\ &=396m-360\cdot3^{k-1}+30\cdot3^{k-1}\\ &=396m-330\cdot3^{k-1}\\ &=11\bigl(36m-30\cdot3^{k-1}\bigr). \end{aligned}

Число в скобках целое: mm целое, а k−1≥0k-1\ge0. Поэтому Ak+1A_{k+1} делится на 1111. База и переход завершены.

№19(4). Выделяем прежнюю пятую степень

Требуется доказать, что An=n5−nA_n=n^5-n делится на 55.

База n=1n=1: A1=15−1=0A_1=1^5-1=0, а 00 кратен 55.

Предположение. Число Ak=k5−kA_k=k^5-k делится на 55.

Цель. Доказать делимость Ak+1=(k+1)5−(k+1)A_{k+1}=(k+1)^5-(k+1).

Раскроем пятую степень. Для этого достаточно обычного умножения многочленов: (k+1)5=(k+1)2(k+1)3(k+1)^5=(k+1)^2(k+1)^3, где

(k+1)2=k2+2k+1,(k+1)3=k3+3k2+3k+1.(k+1)^2=k^2+2k+1, \qquad (k+1)^3=k^3+3k^2+3k+1.

Умножив эти два выражения и собрав одинаковые степени, получаем

(k+1)5=k5+5k4+10k3+10k2+5k+1.(k+1)^5=k^5+5k^4+10k^3+10k^2+5k+1.

Теперь вычтем (k+1)(k+1) и выделим k5−kk^5-k, к которому можно применить предположение:

Ak+1=k5+5k4+10k3+10k2+5k+1−k−1=(k5−k)+(5k4+10k3+10k2+5k)=Ak+5(k4+2k3+2k2+k).\begin{aligned} A_{k+1} &=k^5+5k^4+10k^3+10k^2+5k+1-k-1\\ &=(k^5-k)+(5k^4+10k^3+10k^2+5k)\\ &=A_k+5(k^4+2k^3+2k^2+k). \end{aligned}

Оба слагаемых делятся на 55: первое по предположению, второе из-за множителя 55. Поэтому Ak+1A_{k+1} тоже делится на 55. Утверждение доказано для каждого n≥1n\ge1.

№21. Неравенство Бернулли для одного числа

Требуется доказать

(1+x)n≥1+nx(n∈N, x>−1).(1+x)^n\ge1+nx \qquad(n\in\mathbb N,\ x>-1).

Зафиксируем произвольное x>−1x>-1. Во время индукции меняется показатель nn, а само число xx остаётся одним и тем же.

База n=1n=1. Получается равенство 1+x=1+x1+x=1+x.

Предположение:

(1+x)k≥1+kx.(1+x)^k\ge1+kx.

Цель:

(1+x)k+1≥1+(k+1)x.(1+x)^{k+1}\ge1+(k+1)x.

Так как x>−1x>-1, число 1+x1+x положительно. Умножаем на него доказанное для kk предположение, сохраняя знак:

(1+x)k+1≥(1+kx)(1+x)=1+x+kx+kx2=1+(k+1)x+kx2≥1+(k+1)x.\begin{aligned} (1+x)^{k+1} &\ge(1+kx)(1+x)\\ &=1+x+kx+kx^2\\ &=1+(k+1)x+kx^2\\ &\ge1+(k+1)x. \end{aligned}

Последняя оценка верна при любом допустимом xx: квадрат x2≥0x^2\ge0, а натуральное k>0k>0. Даже если xx отрицательно, добавка kx2kx^2 остаётся неотрицательной.

Цель получена. Индукция доказывает неравенство для любого n≥1n\ge1. Поскольку в начале x>−1x>-1 выбрано произвольно, результат верен для всех указанных в условии xx.

Это также частный случай №20: достаточно взять x1=⋯=xn=xx_1=\cdots=x_n=x; при x=0x=0 сразу имеем равенство. Отдельное доказательство выше показывает, как работает переход непосредственно со степенью.

ПрактикаЗагружаем тест…