Индукция и комбинаторика

Используя индукцию, доказать, что при натуральных $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+x+x^{2}+x^{3}+\ldots +x^{n}=\frac{x^{n+1}-1}{x-1}$ при $x \neq 1$.

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

Найти ошибку в следующем доказательстве «по индукции» утверждения: для всех $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$ коров все животные одного цвета.

Базис: если $n=1$, то стадо состоит из одной коровы, поэтому все коровы одного цвета. Шаг: предположим, что для $n$ утверждение доказано. Рассмотрим стадо из $n+1>1$ коровы. Удалим из этого стада корову $x$, по индукционному предположению все оставшиеся $n$ коров будут одного цвета. Удалим из этого стада другую корову $y$, по индукционному предположению все оставшиеся $n$ коров снова будут одного цвета. Тогда получаем, что цвета коров $x$ и $y$ совпадают с цветами всех остальных коров, поэтому все коровы в стаде одного цвета.

Числа Фибоначчи $F_{i}, i \in \omega$, определяются следующим образом: $F_{i}=i$ при $i<2, F_{i}=F_{i-1}+F_{i-2}$ в противном случае. Доказать, что $F_{i}$ чётно тогда и только тогда, когда $i$ делится на 3.

Доказать для чисел Фибоначчи равенство $F_{i-1} F_{i+1}=F_{i}^{2}+(-1)^{i}$ для $i>0$.

Число $e$ — это сумма ряда $e=\sum_{i=0}^{\infty } 1 / i!$. Пусть $e_{n}$ — сумма первых $n$ членов этого ряда: $e_{n}=\sum_{i<n} 1 / i!$. Доказать, что $A_{n}$ — общее количество размещений без повторений из $n$ предметов по любому количеству мест $m$, равняется $e_{n} n!$. Сделать вывод, что при больши́х $n$ оно приближённо равно en!.

Доказать тождества:

Доказать с помощью индукции формулу бинома Ньютона.

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

где $\lfloor x\rfloor$ и $\lceil x\rceil$ означают округление числа $x$ до ближайшего целого вниз и вверх соответственно.

Доказать, что количество разбиений $n$-элементного множества на $k$ подмножеств, первое из которых содержит $n_{1}$ элементов, второе — $n_{2}$ элементов, $\ldots$, $k$-е — $n_{k}$ элементов, равно $\frac{n!}{n_{1}!n_{2}!\ldots n_{k}!}$.

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

На острове живёт племя туземцев, у которых набор зубов во рту состоит максимально из 30 зубов. При этом на острове нет двух жителей с одинаковыми наборами зубов (наборы одинаковы, если каждый зуб у обоих либо одновременно присутствует, либо одновременно отсутствует). Может ли на этом острове быть больше жителей чем в

Доказать тождество Коши:

Доказать, что число $C_{n}^{k}$ нечётно тогда и только тогда, когда $\rho (k) \subseteq \rho (n)$, где значение функции $\rho (x)$ — это множество двоичных разрядов, которые содержат единицы в двоичной записи числа $x$. Иначе говоря, если в двоичной записи $k$ на каком-то разряде стоит единица, то и в двоичной записи $n$ на этом разряде должна стоять единица. Указание. Использовать индукцию по $n$, представить $n=2^{u}+m$ для $1 \leqslant m \leqslant 2^{u}$ и применить тождество Коши.

Мультимножеством называется неупорядоченный набор элементов, каждый из которых может встречаться в нём сколько угодно раз. Два мультимножества равны, если каждый элемент встречается в них одно и тоже количество раз. Например, мультимножество $\left\{ 1,2,1,3\right\}$ равно мультимножеству $\left\{ 3,1,1,2\right\}$ и не равно мультимножеству $\left\{ 1,2,2,3\right\}$.

Доказать, что количество способов, которыми можно породить $k$-элементное мультимножество, имея $n$ попарно различных элементов и используя каждый из них сколько угодно раз, равно $C_{n+k-1}^{k}$.

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

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

Сколько существует способов расположить $n$ шаров, из них — $m$ чёрных, остальные — белые, в один ряд, чтобы никакие два чёрных шара не оказались рядом?

За круглым столом короля Артура сидят 12 рыцарей. Каждый из них враждует со своими соседями. Нужно выбрать 5 рыцарей, чтобы освободить принцессу. Сколькими способами это можно сделать так, чтобы среди выбранных рыцарей не оказалось врагов?

Решить эту задачу в случае, когда из $n$ рыцарей за столом нужно выбрать $k$ рыцарей.

Доказать принцип включения и исключения в теоретико-множественной форме: если $A_{1}, \ldots , A_{n}$ — это конечные множества, то

Сколько в первой сотне положительных натуральных чисел не делится ни на одно из чисел $2,3,5$? А в первой тысяче чисел?

Определить, сколько целочисленных решений имеет следующая система:

Найти количество перестановок из $n$ элементов, при которых ни один элемент не остаётся в первоначальном положении.