Страница 146 - гдз по алгебре 9 класс учебник Никольский, Потапов

508. Докажите методом математической индукции, что для любого натурального $n$ выполняется неравенство:

а) $1 + 2 + 3 + \dots + n \le n^2$;

б) $2 + 4 + 6 + \dots + 2n < (n + 1)^2$;

в) $\frac{2}{3} \cdot \frac{4}{5} \cdot \frac{6}{7} \cdot \dots \cdot \frac{2n}{2n + 1} > \frac{1}{2n}$;

г) $\frac{1}{2} \cdot \frac{3}{4} \cdot \frac{5}{6} \cdot \dots \cdot \frac{2n - 1}{2n} < \frac{2n}{2n + 1}$;

д) $4^n > 7n - 5$;

е) $2^n > 5n + 1, n \ge 5$.

а) Докажем неравенство $1 + 2 + 3 + \dots + n \le n^2$ методом математической индукции.

1. База индукции.
При $n=1$ неравенство принимает вид $1 \le 1^2$, или $1 \le 1$. Это верное неравенство.

2. Индукционное предположение.
Предположим, что неравенство верно для некоторого натурального числа $k \ge 1$, то есть $1 + 2 + 3 + \dots + k \le k^2$.

3. Индукционный шаг.
Докажем, что неравенство верно и для $n=k+1$, то есть $1 + 2 + 3 + \dots + k + (k+1) \le (k+1)^2$.
Преобразуем левую часть неравенства, используя индукционное предположение:
$(1 + 2 + 3 + \dots + k) + (k+1) \le k^2 + (k+1)$.
Теперь нам нужно доказать, что $k^2 + k + 1 \le (k+1)^2$.
$(k+1)^2 = k^2 + 2k + 1$.
Сравниваем $k^2 + k + 1$ и $k^2 + 2k + 1$:
$k^2 + k + 1 \le k^2 + 2k + 1 \Leftrightarrow k \le 2k \Leftrightarrow 0 \le k$.
Поскольку $k$ — натуральное число, $k \ge 1$, то неравенство $0 \le k$ верно. Следовательно, индукционный шаг доказан.

По принципу математической индукции, неравенство верно для любого натурального $n$.
Ответ: Неравенство доказано.

б) Докажем неравенство $2 + 4 + 6 + \dots + 2n < (n+1)^2$ методом математической индукции.

1. База индукции.
При $n=1$ неравенство принимает вид $2 < (1+1)^2$, или $2 < 4$. Это верное неравенство.

2. Индукционное предположение.
Предположим, что неравенство верно для некоторого натурального числа $k \ge 1$, то есть $2 + 4 + 6 + \dots + 2k < (k+1)^2$.

3. Индукционный шаг.
Докажем, что неравенство верно и для $n=k+1$, то есть $2 + 4 + 6 + \dots + 2k + 2(k+1) < ((k+1)+1)^2 = (k+2)^2$.
Используя индукционное предположение, получаем:
$(2 + 4 + 6 + \dots + 2k) + 2(k+1) < (k+1)^2 + 2(k+1)$.
Докажем, что $(k+1)^2 + 2(k+1) < (k+2)^2$.
$(k+1)^2 + 2(k+1) = k^2 + 2k + 1 + 2k + 2 = k^2 + 4k + 3$.
$(k+2)^2 = k^2 + 4k + 4$.
Неравенство $k^2 + 4k + 3 < k^2 + 4k + 4$ сводится к $3 < 4$, что является верным. Индукционный шаг доказан.

По принципу математической индукции, неравенство верно для любого натурального $n$.
Ответ: Неравенство доказано.

в) Докажем неравенство $\frac{2}{3} \cdot \frac{4}{5} \cdot \frac{6}{7} \cdot \dots \cdot \frac{2n}{2n+1} > \frac{1}{2n}$ методом математической индукции.

1. База индукции.
При $n=1$ неравенство имеет вид $\frac{2}{3} > \frac{1}{2 \cdot 1}$, или $\frac{2}{3} > \frac{1}{2}$. Это верно, так как $4 > 3$.

2. Индукционное предположение.
Пусть для некоторого натурального $k \ge 1$ выполняется неравенство $\frac{2}{3} \cdot \frac{4}{5} \cdot \dots \cdot \frac{2k}{2k+1} > \frac{1}{2k}$.

3. Индукционный шаг.
Докажем, что неравенство верно для $n=k+1$: $\frac{2}{3} \cdot \frac{4}{5} \cdot \dots \cdot \frac{2k}{2k+1} \cdot \frac{2(k+1)}{2(k+1)+1} > \frac{1}{2(k+1)}$.
Левая часть: $(\frac{2}{3} \cdot \dots \cdot \frac{2k}{2k+1}) \cdot \frac{2k+2}{2k+3}$. По предположению индукции, она больше чем $\frac{1}{2k} \cdot \frac{2k+2}{2k+3} = \frac{k+1}{k(2k+3)}$.
Осталось доказать, что $\frac{k+1}{k(2k+3)} > \frac{1}{2(k+1)}$.
Поскольку обе части положительны при $k \ge 1$, можем домножить на знаменатели:
$2(k+1)^2 > k(2k+3) \Leftrightarrow 2(k^2 + 2k + 1) > 2k^2 + 3k \Leftrightarrow 2k^2 + 4k + 2 > 2k^2 + 3k \Leftrightarrow k + 2 > 0$.
Это неравенство верно для всех натуральных $k$. Индукционный шаг доказан.

По принципу математической индукции, неравенство верно для любого натурального $n$.
Ответ: Неравенство доказано.

г) Докажем неравенство $\frac{1}{2} \cdot \frac{3}{4} \cdot \frac{5}{6} \cdot \dots \cdot \frac{2n-1}{2n} < \frac{2n}{2n+1}$ методом математической индукции.

1. База индукции.
При $n=1$ неравенство имеет вид $\frac{1}{2} < \frac{2 \cdot 1}{2 \cdot 1 + 1}$, или $\frac{1}{2} < \frac{2}{3}$. Это верно, так как $3 < 4$.

2. Индукционное предположение.
Пусть для некоторого натурального $k \ge 1$ выполняется неравенство $\frac{1}{2} \cdot \frac{3}{4} \cdot \dots \cdot \frac{2k-1}{2k} < \frac{2k}{2k+1}$.

3. Индукционный шаг.
Докажем, что неравенство верно для $n=k+1$: $\frac{1}{2} \cdot \frac{3}{4} \cdot \dots \cdot \frac{2k-1}{2k} \cdot \frac{2(k+1)-1}{2(k+1)} < \frac{2(k+1)}{2(k+1)+1}$.
Левая часть: $(\frac{1}{2} \cdot \dots \cdot \frac{2k-1}{2k}) \cdot \frac{2k+1}{2k+2}$. По предположению индукции, она меньше чем $\frac{2k}{2k+1} \cdot \frac{2k+1}{2k+2} = \frac{2k}{2k+2} = \frac{k}{k+1}$.
Осталось доказать, что $\frac{k}{k+1} < \frac{2(k+1)}{2k+3}$.
$k(2k+3) < (k+1) \cdot 2(k+1) \Leftrightarrow 2k^2 + 3k < 2(k^2+2k+1) \Leftrightarrow 2k^2 + 3k < 2k^2 + 4k + 2 \Leftrightarrow 0 < k+2$.
Это неравенство верно для всех натуральных $k$. Индукционный шаг доказан.

По принципу математической индукции, неравенство верно для любого натурального $n$.
Ответ: Неравенство доказано.

д) Докажем неравенство $4^n > 7n - 5$ методом математической индукции.

1. База индукции.
При $n=1$ неравенство принимает вид $4^1 > 7 \cdot 1 - 5$, или $4 > 2$. Это верное неравенство.

2. Индукционное предположение.
Предположим, что неравенство верно для некоторого натурального числа $k \ge 1$, то есть $4^k > 7k - 5$.

3. Индукционный шаг.
Докажем, что неравенство верно и для $n=k+1$, то есть $4^{k+1} > 7(k+1) - 5$.
Правая часть равна $7k+7-5 = 7k+2$.
Рассмотрим левую часть: $4^{k+1} = 4 \cdot 4^k$. Используя индукционное предположение, имеем:
$4 \cdot 4^k > 4(7k-5) = 28k - 20$.
Докажем, что $28k - 20 > 7k+2$.
$21k > 22 \Leftrightarrow k > \frac{22}{21}$.
Это неравенство верно для всех $k \ge 2$. Для $k=1$ этот переход не работает. Однако, мы можем использовать другой подход.
$4^{k+1} = 4^k + 3 \cdot 4^k$. По предположению индукции $4^k > 7k-5$.
$4^{k+1} > (7k-5) + 3 \cdot 4^k$. Нам нужно доказать, что $4^{k+1} > 7k+2$.
Достаточно доказать, что $(7k-5) + 3 \cdot 4^k > 7k+2$, что эквивалентно $3 \cdot 4^k > 7$.
При $k=1$, $3 \cdot 4^1 = 12 > 7$. Поскольку $4^k$ — возрастающая функция, неравенство $3 \cdot 4^k > 7$ верно для всех натуральных $k \ge 1$. Индукционный шаг доказан.

По принципу математической индукции, неравенство верно для любого натурального $n$.
Ответ: Неравенство доказано.

е) Докажем неравенство $2^n > 5n + 1$ для $n \ge 5$ методом математической индукции.

1. База индукции.
При $n=5$ (наименьшее значение по условию) неравенство принимает вид $2^5 > 5 \cdot 5 + 1$, или $32 > 26$. Это верное неравенство.

2. Индукционное предположение.
Предположим, что неравенство верно для некоторого натурального числа $k \ge 5$, то есть $2^k > 5k + 1$.

3. Индукционный шаг.
Докажем, что неравенство верно и для $n=k+1$, то есть $2^{k+1} > 5(k+1) + 1$.
Правая часть равна $5k+5+1 = 5k+6$.
Рассмотрим левую часть: $2^{k+1} = 2 \cdot 2^k$. Используя индукционное предположение, имеем:
$2 \cdot 2^k > 2(5k+1) = 10k + 2$.
Теперь докажем, что $10k+2 > 5k+6$.
$5k > 4 \Leftrightarrow k > \frac{4}{5}$.
Поскольку мы рассматриваем $k \ge 5$, неравенство $k > \frac{4}{5}$ очевидно верно. Индукционный шаг доказан.

По принципу математической индукции, неравенство верно для любого натурального $n \ge 5$.
Ответ: Неравенство доказано.

509. Докажите, что для любого натурального n выполняется равенство

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

Докажем данное равенство с помощью метода математической индукции.

Пусть $P(n)$ — это утверждение, что равенство $1^2 + 2^2 + 3^2 + ... + n^2 = \frac{n(n+1)(2n+1)}{6}$ верно.

1. База индукции.

Проверим, выполняется ли утверждение $P(n)$ для $n=1$.

Левая часть равенства: $1^2 = 1$.

Правая часть равенства: $\frac{1(1+1)(2 \cdot 1 + 1)}{6} = \frac{1 \cdot 2 \cdot 3}{6} = \frac{6}{6} = 1$.

Поскольку $1=1$, левая часть равна правой, следовательно, утверждение $P(1)$ истинно.

2. Индукционный переход.

Предположим, что утверждение $P(k)$ истинно для некоторого натурального числа $k$. Это называется индукционным предположением.

Индукционное предположение: $1^2 + 2^2 + 3^2 + ... + k^2 = \frac{k(k+1)(2k+1)}{6}$.

Теперь докажем, что из истинности $P(k)$ следует истинность $P(k+1)$. То есть, нам нужно доказать, что:

$1^2 + 2^2 + 3^2 + ... + k^2 + (k+1)^2 = \frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}$.

Рассмотрим левую часть этого равенства. Мы можем сгруппировать первые $k$ слагаемых:

$(1^2 + 2^2 + 3^2 + ... + k^2) + (k+1)^2$.

Используя индукционное предположение, заменим сумму в скобках:

$\frac{k(k+1)(2k+1)}{6} + (k+1)^2$.

Приведем слагаемые к общему знаменателю и выполним преобразования:

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

Вынесем общий множитель $(k+1)$ в числителе за скобки:

$\frac{(k+1)[k(2k+1) + 6(k+1)]}{6}$.

Упростим выражение в квадратных скобках:

$k(2k+1) + 6(k+1) = 2k^2 + k + 6k + 6 = 2k^2 + 7k + 6$.

Таким образом, левая часть равна:

$\frac{(k+1)(2k^2 + 7k + 6)}{6}$.

Теперь разложим на множители квадратный трехчлен $2k^2 + 7k + 6$. Его корнями являются $k = -2$ и $k = -3/2$. Значит, разложение имеет вид $2(k+2)(k+3/2) = (k+2)(2k+3)$.

Подставим это разложение обратно в наше выражение:

$\frac{(k+1)(k+2)(2k+3)}{6}$.

Это выражение в точности совпадает с правой частью доказываемого равенства для $n=k+1$, так как $\frac{(k+1)((k+1)+1)(2(k+1)+1)}{6} = \frac{(k+1)(k+2)(2k+3)}{6}$.

Шаг индукции доказан. Мы показали, что если утверждение верно для $n=k$, то оно верно и для $n=k+1$.

Заключение.

Так как база индукции верна и индукционный переход доказан, по принципу математической индукции равенство истинно для любого натурального числа $n$.

Ответ: Равенство $1^2 + 2^2 + 3^2 + ... + n^2 = \frac{n(n+1)(2n+1)}{6}$ доказано для всех натуральных $n$.

510. Докажите, что для любого натурального $n$ выполняется равенство

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

Для доказательства данного равенства воспользуемся методом математической индукции.

Пусть $P(n)$ — это утверждение, что $1^3 + 2^3 + 3^3 + \ldots + n^3 = \frac{n^2(n+1)^2}{4}$.

База индукции

Проверим справедливость утверждения для наименьшего натурального числа $n=1$.

Левая часть равенства: $1^3 = 1$.

Правая часть равенства: $\frac{1^2(1+1)^2}{4} = \frac{1 \cdot 2^2}{4} = \frac{4}{4} = 1$.

Так как левая и правая части равны ($1=1$), утверждение $P(1)$ является верным.

Индукционное предположение

Предположим, что утверждение $P(k)$ верно для некоторого произвольного натурального числа $k \ge 1$.

То есть, мы предполагаем истинность равенства: $1^3 + 2^3 + 3^3 + \ldots + k^3 = \frac{k^2(k+1)^2}{4}$.

Индукционный шаг

Докажем, что если утверждение $P(k)$ верно, то верно и утверждение $P(k+1)$. Иными словами, докажем, что:

$1^3 + 2^3 + 3^3 + \ldots + k^3 + (k+1)^3 = \frac{(k+1)^2((k+1)+1)^2}{4}$.

Рассмотрим левую часть этого равенства. Её можно представить в виде суммы первых $k$ членов и $(k+1)$-го члена:

$(1^3 + 2^3 + \ldots + k^3) + (k+1)^3$.

Согласно индукционному предположению, заменим сумму в скобках:

$\frac{k^2(k+1)^2}{4} + (k+1)^3$.

Преобразуем полученное выражение. Вынесем за скобки общий множитель $(k+1)^2$:

$(k+1)^2 \left( \frac{k^2}{4} + (k+1) \right)$.

Приведем слагаемые в скобках к общему знаменателю:

$(k+1)^2 \left( \frac{k^2}{4} + \frac{4(k+1)}{4} \right) = (k+1)^2 \left( \frac{k^2 + 4k + 4}{4} \right)$.

Выражение в числителе дроби, $k^2 + 4k + 4$, является полным квадратом двучлена $(k+2)$.

Таким образом, мы получаем:

$\frac{(k+1)^2(k+2)^2}{4}$.

Это выражение в точности совпадает с правой частью доказываемого равенства для $n=k+1$, так как $(k+1)+1=k+2$.

Следовательно, мы доказали, что из истинности $P(k)$ следует истинность $P(k+1)$.

Поскольку база индукции и индукционный шаг выполнены, по принципу математической индукции равенство верно для любого натурального числа $n$.

Ответ: Равенство $1^3 + 2^3 + 3^3 + \ldots + n^3 = \frac{n^2(n+1)^2}{4}$ для любого натурального $n$ доказано.

511. Задача аль-Караджи (Иран, XI в.)

Докажите, что для любого натурального $n$ выполняется равенство

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

Для доказательства данного тождества, известного как тождество Никомаха, воспользуемся методом математической индукции.

Доказываемое утверждение $P(n)$ имеет вид:

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

Сумма первых $n$ натуральных чисел в правой части является суммой арифметической прогрессии и равна $S_n = \frac{n(n+1)}{2}$. Подставив это в исходное равенство, получим формулу, которую будем доказывать:

$\sum_{i=1}^{n} i^3 = \left(\frac{n(n+1)}{2}\right)^2$

Доказательство состоит из двух шагов.

Шаг 1: База индукции

Проверим справедливость утверждения для наименьшего натурального числа $n=1$.

Левая часть равенства: $1^3 = 1$.

Правая часть равенства: $(1)^2 = 1$.

Поскольку $1=1$, утверждение $P(1)$ истинно.

Шаг 2: Индукционный переход

Индукционное предположение: предположим, что утверждение $P(k)$ справедливо для некоторого произвольного натурального числа $k \ge 1$. То есть, мы считаем верным равенство:

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

или, в другой записи:

$\sum_{i=1}^{k} i^3 = \left(\frac{k(k+1)}{2}\right)^2$

Индукционный шаг: докажем, что из истинности $P(k)$ следует истинность $P(k+1)$. Нам нужно доказать, что:

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

Рассмотрим левую часть этого равенства. Сгруппируем первые $k$ слагаемых:

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

Согласно индукционному предположению, заменим сумму в скобках:

$L = \left(\frac{k(k+1)}{2}\right)^2 + (k+1)^3$

Теперь преобразуем это выражение. Раскроем скобки и вынесем общий множитель $(k+1)^2$:

$L = \frac{k^2(k+1)^2}{4} + (k+1)^3 = (k+1)^2 \left(\frac{k^2}{4} + (k+1)\right)$

Приведем выражение в скобках к общему знаменателю:

$L = (k+1)^2 \left(\frac{k^2 + 4(k+1)}{4}\right) = (k+1)^2 \left(\frac{k^2 + 4k + 4}{4}\right)$

Выражение $k^2 + 4k + 4$ является полным квадратом $(k+2)^2$. Тогда:

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

Это выражение можно записать как квадрат дроби:

$L = \left(\frac{(k+1)(k+2)}{2}\right)^2$

Теперь рассмотрим правую часть доказываемого равенства для $n=k+1$. Сумма в скобках — это сумма первых $k+1$ натуральных чисел:

$R = (1 + 2 + \dots + k + (k+1))^2 = \left(\frac{(k+1)((k+1)+1)}{2}\right)^2 = \left(\frac{(k+1)(k+2)}{2}\right)^2$

Мы видим, что преобразованная левая часть $L$ равна правой части $R$. Таким образом, мы доказали, что если утверждение верно для $k$, то оно верно и для $k+1$.

Поскольку оба шага метода математической индукции выполнены, исходное равенство справедливо для любого натурального числа $n$.

Ответ: Равенство $1^3 + 2^3 + 3^3 + \dots + n^3 = (1 + 2 + 3 + \dots + n)^2$ доказано для всех натуральных $n$.

512. Задача аль-Каши (XIV–XV вв.). Докажите, что для любого натурального $n$ выполняется равенство

$1^4 + 2^4 + 3^4 + \dots + n^4 = \frac{1}{30}(6n^5 + 15n^4 + 10n^3 - n)$

Докажем данное равенство методом математической индукции.

Обозначим сумму в левой части как $S_n = 1^4 + 2^4 + 3^4 + \dots + n^4$. Требуется доказать, что для любого натурального $n$ выполняется равенство $S_n = \frac{1}{30}(6n^5 + 15n^4 + 10n^3 - n)$.

1. Базис индукции

Проверим справедливость равенства для наименьшего натурального числа $n=1$.

Левая часть равенства: $S_1 = 1^4 = 1$.

Правая часть равенства: $\frac{1}{30}(6 \cdot 1^5 + 15 \cdot 1^4 + 10 \cdot 1^3 - 1) = \frac{1}{30}(6 + 15 + 10 - 1) = \frac{30}{30} = 1$.

Поскольку $1 = 1$, левая и правая части совпадают. Равенство верно для $n=1$.

2. Индукционное предположение

Предположим, что равенство верно для некоторого натурального числа $n=k$, где $k \ge 1$. То есть, мы считаем верным, что:

$S_k = 1^4 + 2^4 + \dots + k^4 = \frac{1}{30}(6k^5 + 15k^4 + 10k^3 - k)$.

3. Индукционный шаг

Докажем, что если равенство верно для $n=k$, то оно верно и для следующего натурального числа $n=k+1$. То есть, нам нужно доказать:

$S_{k+1} = \frac{1}{30}(6(k+1)^5 + 15(k+1)^4 + 10(k+1)^3 - (k+1))$.

Рассмотрим левую часть этого равенства, $S_{k+1}$:

$S_{k+1} = 1^4 + 2^4 + \dots + k^4 + (k+1)^4 = S_k + (k+1)^4$.

Воспользуемся индукционным предположением для $S_k$:

$S_{k+1} = \frac{1}{30}(6k^5 + 15k^4 + 10k^3 - k) + (k+1)^4$.

Приведем выражение к общему знаменателю 30:

$S_{k+1} = \frac{1}{30}[ (6k^5 + 15k^4 + 10k^3 - k) + 30(k+1)^4 ]$.

Раскроем $(k+1)^4$ по формуле бинома Ньютона: $(k+1)^4 = k^4 + 4k^3 + 6k^2 + 4k + 1$.

Тогда $30(k+1)^4 = 30k^4 + 120k^3 + 180k^2 + 120k + 30$.

Подставим это в наше выражение для $S_{k+1}$:

$S_{k+1} = \frac{1}{30}[ (6k^5 + 15k^4 + 10k^3 - k) + (30k^4 + 120k^3 + 180k^2 + 120k + 30) ]$.

Сгруппируем слагаемые по степеням $k$ внутри скобок:

$S_{k+1} = \frac{1}{30}[ 6k^5 + (15+30)k^4 + (10+120)k^3 + 180k^2 + (-1+120)k + 30 ]$.

$S_{k+1} = \frac{1}{30}(6k^5 + 45k^4 + 130k^3 + 180k^2 + 119k + 30)$.

Теперь преобразуем правую часть доказываемого равенства для $n=k+1$, чтобы показать, что она равна полученному выражению.

Правая часть: $P(k+1) = \frac{1}{30}(6(k+1)^5 + 15(k+1)^4 + 10(k+1)^3 - (k+1))$.

Раскроем степени биномов:

$6(k+1)^5 = 6(k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1) = 6k^5 + 30k^4 + 60k^3 + 60k^2 + 30k + 6$.

$15(k+1)^4 = 15(k^4 + 4k^3 + 6k^2 + 4k + 1) = 15k^4 + 60k^3 + 90k^2 + 60k + 15$.

$10(k+1)^3 = 10(k^3 + 3k^2 + 3k + 1) = 10k^3 + 30k^2 + 30k + 10$.

$-(k+1) = -k - 1$.

Сложим все полученные многочлены:

$6k^5 + (30+15)k^4 + (60+60+10)k^3 + (60+90+30)k^2 + (30+60+30-1)k + (6+15+10-1)$

$= 6k^5 + 45k^4 + 130k^3 + 180k^2 + 119k + 30$.

Таким образом, правая часть равна $\frac{1}{30}(6k^5 + 45k^4 + 130k^3 + 180k^2 + 119k + 30)$.

Мы получили, что преобразованная левая часть для $n=k+1$ совпадает с преобразованной правой частью. Следовательно, индукционный шаг доказан.

Вывод

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

Ответ: Равенство доказано методом математической индукции.

513. Задача Фаульхабера (Германия, 1580–1635). Докажите, что

для любого натурального n выполняется равенство

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

Докажем данное равенство методом математической индукции.

База индукции. Проверим справедливость утверждения для $n=1$.
Левая часть равенства: $S_1 = 1^5 = 1$.
Правая часть равенства: $\frac{1}{12}(2 \cdot 1^6 + 6 \cdot 1^5 + 5 \cdot 1^4 - 1^2) = \frac{1}{12}(2 + 6 + 5 - 1) = \frac{12}{12} = 1$.
Так как $1=1$, равенство верно для $n=1$.

Индукционное предположение. Предположим, что равенство верно для некоторого натурального числа $n=k$, где $k \ge 1$. То есть, предположим, что:$$1^5 + 2^5 + \dots + k^5 = \frac{1}{12}(2k^6 + 6k^5 + 5k^4 - k^2)$$

Индукционный шаг. Докажем, что из этого следует справедливость равенства для $n=k+1$. То есть, нам нужно доказать:$$1^5 + 2^5 + \dots + k^5 + (k+1)^5 = \frac{1}{12}(2(k+1)^6 + 6(k+1)^5 + 5(k+1)^4 - (k+1)^2)$$

Рассмотрим левую часть $S_{k+1}$ этого равенства. Используя индукционное предположение, мы можем заменить сумму первых $k$ слагаемых:$$S_{k+1} = (1^5 + 2^5 + \dots + k^5) + (k+1)^5 = \frac{1}{12}(2k^6 + 6k^5 + 5k^4 - k^2) + (k+1)^5$$Приведем к общему знаменателю:$$S_{k+1} = \frac{(2k^6 + 6k^5 + 5k^4 - k^2) + 12(k+1)^5}{12}$$Раскроем $(k+1)^5$ по формуле бинома Ньютона:$$(k+1)^5 = k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1$$Тогда $12(k+1)^5 = 12k^5 + 60k^4 + 120k^3 + 120k^2 + 60k + 12$.
Подставим это выражение в числитель для $S_{k+1}$ и приведем подобные слагаемые:$$ \text{Числитель левой части} = (2k^6 + 6k^5 + 5k^4 - k^2) + (12k^5 + 60k^4 + 120k^3 + 120k^2 + 60k + 12) $$$$ = 2k^6 + (6+12)k^5 + (5+60)k^4 + 120k^3 + (-1+120)k^2 + 60k + 12 $$$$ = 2k^6 + 18k^5 + 65k^4 + 120k^3 + 119k^2 + 60k + 12 $$

Теперь преобразуем правую часть доказываемого равенства для $n=k+1$:$$ F(k+1) = \frac{1}{12}(2(k+1)^6 + 6(k+1)^5 + 5(k+1)^4 - (k+1)^2) $$Раскроем скобки в числителе, используя разложения по биному Ньютона:$(k+1)^6 = k^6 + 6k^5 + 15k^4 + 20k^3 + 15k^2 + 6k + 1$$(k+1)^5 = k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1$$(k+1)^4 = k^4 + 4k^3 + 6k^2 + 4k + 1$$(k+1)^2 = k^2 + 2k + 1$

Подставим эти разложения в выражение для числителя правой части:$$ \text{Числитель правой части} = 2(k^6 + 6k^5 + \dots) + 6(k^5 + 5k^4 + \dots) + 5(k^4 + \dots) - (k^2 + \dots) $$Сгруппируем слагаемые по степеням $k$:
$k^6: 2 \cdot 1 = 2$
$k^5: 2 \cdot 6 + 6 \cdot 1 = 12 + 6 = 18$
$k^4: 2 \cdot 15 + 6 \cdot 5 + 5 \cdot 1 = 30 + 30 + 5 = 65$
$k^3: 2 \cdot 20 + 6 \cdot 10 + 5 \cdot 4 = 40 + 60 + 20 = 120$
$k^2: 2 \cdot 15 + 6 \cdot 10 + 5 \cdot 6 - 1 = 30 + 60 + 30 - 1 = 119$
$k^1: 2 \cdot 6 + 6 \cdot 5 + 5 \cdot 4 - 2 = 12 + 30 + 20 - 2 = 60$
$k^0: 2 \cdot 1 + 6 \cdot 1 + 5 \cdot 1 - 1 = 2 + 6 + 5 - 1 = 12$
Таким образом, числитель правой части равен:$$ 2k^6 + 18k^5 + 65k^4 + 120k^3 + 119k^2 + 60k + 12 $$

Мы получили, что числитель левой части и числитель правой части равны. Следовательно, $S_{k+1} = F(k+1)$, и равенство для $n=k+1$ верно.

Индукционный переход доказан. По принципу математической индукции, исходное равенство справедливо для любого натурального числа $n$.

Ответ: Доказательство справедливости равенства для любого натурального $n$ приведено выше методом математической индукции.

514. Докажите, что для любого натурального n:

а) $5^n + 3$ делится на 4;

б) $7^n + 5$ делится на 6;

в) $4^n + 6n - 1$ делится на 9;

г) $5^n + 4n - 1$ делится на 8.

Для доказательства данных утверждений для любого натурального $n$ воспользуемся методом математической индукции.

Докажем, что выражение $5^n + 3$ делится на 4 для любого натурального $n$.

1. База индукции:
Проверим утверждение для $n=1$.
$5^1 + 3 = 5 + 3 = 8$.
Число 8 делится на 4 ($8 = 4 \cdot 2$), следовательно, утверждение верно для $n=1$.

2. Индукционное предположение:
Предположим, что утверждение верно для некоторого натурального числа $k$, то есть $5^k + 3$ делится на 4. Это означает, что существует такое целое число $m$, что $5^k + 3 = 4m$. Из этого равенства выразим $5^k = 4m - 3$.

3. Индукционный переход:
Докажем, что утверждение верно для $n = k+1$, то есть что $5^{k+1} + 3$ делится на 4.
Рассмотрим выражение $5^{k+1} + 3$: $5^{k+1} + 3 = 5 \cdot 5^k + 3$.
Подставим выражение для $5^k$ из индукционного предположения: $5(4m - 3) + 3 = 20m - 15 + 3 = 20m - 12$.
Вынесем общий множитель 4 за скобки: $20m - 12 = 4(5m - 3)$.
Поскольку $m$ — целое число, то $5m - 3$ также является целым числом. Следовательно, выражение $4(5m - 3)$ делится на 4.

Таким образом, по принципу математической индукции, утверждение, что $5^n + 3$ делится на 4, верно для всех натуральных $n$.

Ответ: Утверждение доказано.

Докажем, что выражение $7^n + 5$ делится на 6 для любого натурального $n$.

1. База индукции:
Проверим утверждение для $n=1$.
$7^1 + 5 = 7 + 5 = 12$.
Число 12 делится на 6 ($12 = 6 \cdot 2$), следовательно, утверждение верно для $n=1$.

2. Индукционное предположение:
Предположим, что утверждение верно для некоторого натурального числа $k$, то есть $7^k + 5$ делится на 6. Это означает, что существует такое целое число $m$, что $7^k + 5 = 6m$. Отсюда $7^k = 6m - 5$.

3. Индукционный переход:
Докажем, что утверждение верно для $n = k+1$, то есть что $7^{k+1} + 5$ делится на 6.
$7^{k+1} + 5 = 7 \cdot 7^k + 5$.
Подставим $7^k = 6m - 5$: $7(6m - 5) + 5 = 42m - 35 + 5 = 42m - 30$.
Вынесем 6 за скобки: $42m - 30 = 6(7m - 5)$.
Так как $m$ — целое число, $7m - 5$ тоже целое, и выражение $6(7m - 5)$ делится на 6.

По принципу математической индукции, утверждение, что $7^n + 5$ делится на 6, верно для всех натуральных $n$.

Ответ: Утверждение доказано.

Докажем, что выражение $4^n + 6n - 1$ делится на 9 для любого натурального $n$.

1. База индукции:
Проверим для $n=1$.
$4^1 + 6(1) - 1 = 4 + 6 - 1 = 9$.
Число 9 делится на 9 ($9 = 9 \cdot 1$), утверждение верно для $n=1$.

2. Индукционное предположение:
Предположим, что для некоторого натурального $k$ выражение $4^k + 6k - 1$ делится на 9. То есть существует целое число $m$ такое, что $4^k + 6k - 1 = 9m$. Отсюда $4^k = 9m - 6k + 1$.

3. Индукционный переход:
Докажем, что утверждение верно для $n = k+1$, то есть $4^{k+1} + 6(k+1) - 1$ делится на 9.
$4^{k+1} + 6(k+1) - 1 = 4 \cdot 4^k + 6k + 6 - 1 = 4 \cdot 4^k + 6k + 5$.
Подставим $4^k = 9m - 6k + 1$: $4(9m - 6k + 1) + 6k + 5 = 36m - 24k + 4 + 6k + 5 = 36m - 18k + 9$.
Вынесем 9 за скобки: $36m - 18k + 9 = 9(4m - 2k + 1)$.
Так как $m$ и $k$ — целые числа, выражение в скобках является целым числом, и, следовательно, $9(4m - 2k + 1)$ делится на 9.

По принципу математической индукции, утверждение, что $4^n + 6n - 1$ делится на 9, верно для всех натуральных $n$.

Ответ: Утверждение доказано.

Докажем, что выражение $5^n + 4n - 1$ делится на 8 для любого натурального $n$.

1. База индукции:
Проверим для $n=1$.
$5^1 + 4(1) - 1 = 5 + 4 - 1 = 8$.
Число 8 делится на 8 ($8 = 8 \cdot 1$), утверждение верно для $n=1$.

2. Индукционное предположение:
Предположим, что для некоторого натурального $k$ выражение $5^k + 4k - 1$ делится на 8. То есть существует целое число $m$ такое, что $5^k + 4k - 1 = 8m$. Отсюда $5^k = 8m - 4k + 1$.

3. Индукционный переход:
Докажем, что утверждение верно для $n = k+1$, то есть $5^{k+1} + 4(k+1) - 1$ делится на 8.
$5^{k+1} + 4(k+1) - 1 = 5 \cdot 5^k + 4k + 4 - 1 = 5 \cdot 5^k + 4k + 3$.
Подставим $5^k = 8m - 4k + 1$: $5(8m - 4k + 1) + 4k + 3 = 40m - 20k + 5 + 4k + 3 = 40m - 16k + 8$.
Вынесем 8 за скобки: $40m - 16k + 8 = 8(5m - 2k + 1)$.
Так как $m$ и $k$ — целые числа, выражение в скобках является целым числом, и, следовательно, $8(5m - 2k + 1)$ делится на 8.

По принципу математической индукции, утверждение, что $5^n + 4n - 1$ делится на 8, верно для всех натуральных $n$.

Ответ: Утверждение доказано.

515. Докажите, что:

a) $7^n + 9$ делится на 8 для любого нечётного натурального $n$;

б) $3^n + 7$ делится на 8 для любого чётного натурального $n$.

а)

Чтобы доказать, что выражение $7^n + 9$ делится на 8 для любого нечётного натурального $n$, воспользуемся методом сравнений по модулю. Нам необходимо показать, что $7^n + 9$ даёт остаток 0 при делении на 8, то есть $7^n + 9 \equiv 0 \pmod{8}$.

Рассмотрим остатки от деления на 8 для каждого слагаемого. Число 7 можно представить как $8-1$, поэтому $7 \equiv -1 \pmod{8}$. Число 9 можно представить как $8+1$, поэтому $9 \equiv 1 \pmod{8}$.

Подставим эти сравнения в исходное выражение: $7^n + 9 \equiv (-1)^n + 1 \pmod{8}$

По условию задачи, $n$ — нечётное натуральное число (например, 1, 3, 5, ...). Для любого нечётного $n$ степень $(-1)^n$ равна -1. Следовательно, выражение $(-1)^n + 1$ принимает значение $-1 + 1 = 0$.

Таким образом, мы показали, что $7^n + 9 \equiv 0 \pmod{8}$. Это означает, что $7^n + 9$ делится на 8 без остатка для любого нечётного натурального $n$.

Ответ: Утверждение доказано.

б)

Чтобы доказать, что выражение $3^n + 7$ делится на 8 для любого чётного натурального $n$, также воспользуемся сравнениями по модулю 8. Нам необходимо показать, что $3^n + 7 \equiv 0 \pmod{8}$.

Поскольку $n$ — чётное натуральное число, его можно представить в виде $n = 2k$, где $k$ — натуральное число ($k \ge 1$). Тогда выражение $3^n$ можно преобразовать: $3^n = 3^{2k} = (3^2)^k = 9^k$.

Рассмотрим слагаемые по модулю 8. Так как $9 \equiv 1 \pmod{8}$, то для любого натурального $k$ справедливо $9^k \equiv 1^k \equiv 1 \pmod{8}$. Таким образом, $3^n \equiv 1 \pmod{8}$ для любого чётного $n$. Для второго слагаемого имеем $7 \equiv -1 \pmod{8}$.

Складывая сравнения для обоих слагаемых, получаем: $3^n + 7 \equiv 1 + (-1) \equiv 0 \pmod{8}$

Это означает, что $3^n + 7$ делится на 8 без остатка для любого чётного натурального $n$.

Ответ: Утверждение доказано.

516. На один из трёх штырьков насажены $n$ различных колец так, что большее кольцо лежит ниже меньшего (на рисунке 62 $n = 3$). За один ход разрешается перенести одно кольцо с одного штырька на другой, при этом не разрешается большее кольцо класть на меньшее. Докажите, что наименьшее число ходов, за которое можно перенести все кольца с одного штырька на другой, равно $2^n - 1$.

Рис. 62

Для доказательства того, что наименьшее число ходов, за которое можно перенести все $n$ колец с одного штырька на другой, равно $2^n - 1$, воспользуемся методом математической индукции.

Обозначим через $H(n)$ минимальное число ходов, необходимое для перемещения $n$ колец с одного штырька на другой.

Базис индукции:

Проверим утверждение для $n=1$. Если у нас есть только одно кольцо, то для его переноса на другой штырек потребуется ровно один ход.По формуле получаем: $H(1) = 2^1 - 1 = 2 - 1 = 1$.Утверждение верно для $n=1$.

Индукционное предположение:

Предположим, что для переноса $k$ колец наименьшее число ходов действительно равно $H(k) = 2^k - 1$ для некоторого натурального числа $k \ge 1$.

Индукционный шаг:

Докажем, что утверждение верно для $n = k + 1$, то есть $H(k+1) = 2^{k+1} - 1$.Рассмотрим башню из $k+1$ кольца. Пусть штырьки называются A (исходный), B (вспомогательный) и C (целевой). Чтобы переместить самое большое, $(k+1)$-е кольцо со штырька A на штырек C, необходимо, чтобы на штырьке C не было других колец, и чтобы на штырьке A, кроме самого большого кольца, также не было других колец. Это означает, что все верхние $k$ колец должны быть перемещены на вспомогательный штырек B.

Таким образом, процесс переноса $k+1$ кольца разбивается на три обязательных этапа:

1. Перенести башню из верхних $k$ колец с исходного штырька A на вспомогательный штырек B. Согласно нашему индукционному предположению, минимальное число ходов для этого составляет $H(k) = 2^k - 1$.
2. Перенести самое большое, $(k+1)$-е кольцо, с исходного штырька A на целевой штырек C. Это действие занимает ровно 1 ход.
3. Перенести башню из $k$ колец со вспомогательного штырька B на целевой штырек C, поверх самого большого кольца. Это снова займет $H(k) = 2^k - 1$ ходов.

Следовательно, общее минимальное число ходов для $k+1$ кольца равно сумме ходов на всех этапах:

$H(k+1) = H(k) + 1 + H(k) = 2 \cdot H(k) + 1$

Теперь подставим в это выражение значение $H(k)$ из нашего индукционного предположения:

$H(k+1) = 2 \cdot (2^k - 1) + 1 = 2 \cdot 2^k - 2 + 1 = 2^{k+1} - 1$

Мы получили формулу для $n = k+1$. Таким образом, мы доказали, что если формула верна для $k$, то она верна и для $k+1$.

Заключение:

По принципу математической индукции, формула верна для любого натурального числа $n$.

Ответ: Наименьшее число ходов, необходимое для переноса $n$ колец, составляет $2^n - 1$, что и требовалось доказать.