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

Используя индукцию, доказать, что

Используя индукцию, доказать, что при натуральных $n$

Доказать, что $1^{4}+2^{4}+\ldots +n^{4}=\frac{1}{30} n(n+1)(2 n+1)\left(3 n^{2}+3 n-1\right)$.

Доказать, что $1 \cdot 2+2 \cdot 3+\ldots +n(n+1)=\frac{n(n+1)(n+2)}{3}$.

Доказать, что $(1+2+3+\cdots +n)^{2}=1^{3}+2^{3}+3^{3}+\cdots +n^{3}$.

Доказать, что

Доказать, что $1+x+x^{2}+x^{3}+\ldots +x^{n}=\frac{x^{n+1}-1}{x-1}$ при $x \neq 1$.

Доказать формулу Муавра для натуральных степеней комплексного числа: если $z=r(\cos \varphi +i \sin \varphi )$, то $z^{n}=r^{n}(\cos n \varphi +i \sin n \varphi )$. Здесь $i$ — мнимая единица, $i^{2}=-1, r$ и $\varphi$ — действительные числа, $r \geqslant 0$.

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

Доказать, что $n$ различных прямых на плоскости, никакие две из которых не параллельны и никакие три из которых не пересекаются в одной точке, разбивают плоскость на $\left(n^{2}+n+2\right) / 2$ областей.

Пусть в выпуклом $n$-угольнике, $n \geqslant 4$, никакие три диагонали не пересекаются в одной точке. Доказать, что в нём имеется $D(n)=\frac{(n-3)(n-2)(n-1) n}{24}$ точек пересечения диагоналей.

Доказать, что если стоимость некоторого письма больше или равна 6 рублей, то его можно точно оплатить, используя двух- и семирублёвые марки.

Найти ошибку в следующем доказательстве «по индукции» утверждения: для всех $n \geqslant 1$ справедливо неравенство $3^{n}>3(n+1)+1$.

Пусть для некоторого $k \geqslant 1$ неравенство справедливо, то есть $3^{k}>3(k+1)+1$, обозначим это неравенство (*). Докажем, что оно верно и для $n=k+1$, то есть $3^{k+1}>3(k+2)+1$. Для этого заметим, что для любого $k \geqslant 1$ верно неравенство $2 \cdot 3^{k}>3$. Прибавив его левую и правую часть к соответствующим частям неравенства $(*)$, получим $3^{k}+2 \cdot 3^{k}>3(k+1)+1+3$ или $3^{k+1}>3(k+2)+1$, что и требовалось.

Установить, при каких $n$ справедливо неравенство $3^{n}>3(n+1)+1$ на самом деле.

Найти ошибку в доказательстве «по индукции» следующего утверждения. Пусть $n$ окружностей на плоскости расположены так, что любые две из них имеют ровно две общие точки, а для любой третьей окружности $O$ одна из этих точек лежит внутри $O$, а другая — снаружи $O$. Тогда плоскость делится этими окружностями на $N(n)=1+n(n-1)$ частей.

Базис: если $n=0$, то имеется только одна часть. Шаг: пусть для $n$ окружностей утверждение верно, $N(n)=1+n(n-1)$. Тогда $(n+1)$-я окружность имеет $2 n$ точек пересечения с предыдущими (с каждой по две). Следовательно, она проходит через $2 n$ областей и делит каждую из них на две. Поэтому количество областей возрастает на $2 n$ и мы получаем $N(n+1)=N(n)+2 n=1+n(n-1)+2 n=1+(n+1) n$.

Установить настоящее значение $N(n)$.

Пусть $n \geqslant 1$ сфер в пространстве расположены так, что любые три из них имеют ровно две общие точки, а для любой четвёртой сферы $S$ одна из этих точек лежит внутри $S$, а другая снаружи $S$. Доказать, что пространство делится этими сферами на $N(n)=2 n+\frac{n(n-1)(n-2)}{3}$ кусков.

Предположим, что некоторая колония бактерий $\mathcal{C}$ состоит из конечного количества особей, для каждой из которых указано натуральное число — максимальное количество делений, которое бактерия может пережить, то есть $\mathcal{C}=\left\{ (b, t): b \text{ — идентификатор бактерии, } t \text{ — максимальное количество делений}\right\}$.

На каждом шаге в жизни колонии происходит одно событие: выбирается какая-нибудь одна бактерия $(b, t)$ и, если $t=0$, то она удаляется из колонии («умирает»), а если $t>0$, то эта бактерия заменяется на некоторое конечное множество бактерий («делится»), при этом все её потомки способны к делению менее $t$ раз.

Доказать, что любая такая колония $\mathcal{C}$ в конце концов станет пустой («вымрет»). Указание. Использовать индукцию по максимальному количеству делений $T: T=\max \left\{ t:(b, t) \in \mathcal{C}\right\}$, а внутри — индукцию по количеству таких бактерий.

Числа Фибоначчи определяются следующими рекуррентными соотношениями: $F_{0}=0, F_{1}=1, F_{n+2}=F_{n+1}+F_{n}$. Доказать, что

Доказать, что при $n \geqslant 1$

Доказать, что существует $F_{n+2}$ последовательностей нулей и единиц длины $n$, в которых нет двух единиц подряд.

Задача о Ханойских башнях. Имеется три стержня. На один из них надето несколько дисков, диаметры которых убывают снизу вверх (получается детская пирамидка). Разрешается перекладывать верхний диск с любого стержня на любой другой, но при этом запрещено класть диск большего диаметра на диск меньшего диаметра. Требуется перенести всю пирамидку на другой стержень.

Корректность алгоритма Евклида нахождения наибольшего общего делителя натуральных чисел основана на таком утверждении: НОД $\left\{ x, y\right\} =$ НОД $\left\{ x-y, y\right\}$ при $y \leqslant x$. Используя это же утверждение, доказать, что существуют целые $a$ и $b$ такие, что НОД $\left\{ x, y\right\} =a x+b y$. Указание. Использовать индукцию по $x+y$ для фиксированного $d=$ НОД $\left\{ x, y\right\}$.