Ничего не нашлось!
Попробуйте переформулировать запрос.
Вы можете предложить добавить решение/материал.
Свойства подпоследовательностей

Содержимое задачи.

К решению
Задача 5
Нормальная

Пусть

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

где — число сочетаний из элементов по . Вывести отсюда формулу бинома Ньютона.

Указание

Доказательство равенства

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

Выполните следующее преобразование:

В правой части выполните замену на индукционное предположение:

Умножьте скобку на каждый член суммы и воспользуйтесь свойствами сочетаний:

Бином Ньютона

Воспользуйтесь доказанным равенством и тем фактом, что при :

Решение
Что вообще такое ?

Сначала разберемся, что вообще такое . Запишем данное в условии определение чуть более понятным образом:

Короче, это просто некоторая операция, похожая на степень. Плюс, эта операция зависит от какого-то числа .

Пример выражения при :

Пример выражения :

Сразу стоит прояснить важный частный случай, когда :

Другими словами, при выражение является обычным возведением в степень .

Теперь докажем следующее равенство для всех натуральных :

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

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

Пусть .

В левой части равенства получаем:

В правой:

так как и (по условию). Итак, база индукции выполняется.

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

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

Докажем, что равенство выполняется и для :

Рассмотрим левую часть равенства и примем :

Замечаем, что все множители кроме последнего по определению образуют :

Возвращаемся от обратно к :

Исходя из предположения индукционного перехода мы можем заменить на сумму:

Итак, скобка умножается на каждое слагаемое из суммы. Распишем несколько подобных умножений.

Для первого слагаемого ():

Для второго слагаемого ():

Для последнего слагаемого ():

То есть, для каждого слагаемого мы раскладываем скобку так, чтобы увеличить степень и степень . Соберем все эти слагаемые вместе:

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

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

Получаем итоговую сумму:

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

Итак, мы доказали, что для всех натуральных чисел верна формула:

Вывод формулы бинома Ньютона

В самом начале решения мы установили, что если , то . Так вот, доказанная формула при принимает вид:

А это и есть формула бинома Ньютона.