Тема . Математический анализ

.15 Последовательности. Индукция.

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела математический анализ

Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#37944

Доказать следующие свойства биномиальных коэффициентов ( для любых $n$ и $k$ таких, что $1 ≤ k ≤ n$ ):

a) $(n) (n ) k = n− k$

b) $(n)+ (n ) = (n+1) k k+1 k+1$

c) $n∑ ( ) ( ) ( ) ( ) ( ) ( ) ( ) nk = nn + nn−1 + nn−2 + ⋅⋅⋅+ nk + ⋅⋅⋅+ n1 + n0 = 2n k=0$ (пользуясь исключительно комбинаторным определением! т.е. без бинома Ньютона)

d) $(n) k$ возрастает по $n$ при фиксированном $k$

e)* Фиксируем $n.$ Найти такое $k,$ при котором $( ) nk$ максимально.

Показать ответ и решение

a) Как мы помним, $(n) k$ равно числу подмножеств размера $k$ у $n$ -элементного множества $S.$ Но любому $k$ -элементному подмножеству $A ⊂ S$ можно однозначно сопоставить $(n − k)$ -элементное подмножество $¯A$ в $S.$ Другими словами, выбрать $k$ элементов из $n$ возможных – это то же самое, что из $n$ -элементного множества ”выкинуть” $\text{[math]}$ $n − k$ элементов.

По формуле для $(n) k$ всё совсем очевидно.
Поскольку $( ) nk = k!(nn!−k)!,$ то $( ) nn−k = (n−nk!)!(k)! = k!(nn−!k)!,$ так как наша формула $--n!-- k!(n−k)!$ очевидно симметрична относительно замены $k$ на $n− k.$

b) Это легко доказать просто поигравшись с формулой $( ) nk = k!(nn−!k)!.$
Действительно: $(n) (n ) --n!-- -----n!---- приведём к общ. знам. n!(k+1)+n!(n−k) k + k+1 = k!(n− k)! + (k+1)!(n−k−1)! = (k+1)!(n−k)! =$
$( ) = n!(((kk++11))!+(n(−n−k)k!)) = (k+n1!()n!(+n1)−k)! = (k+(1n)+!(1n)!−k)! = n+k+11$

c)В левой стороне равенства мы суммируем количество способов выбрать:

$n$ -элементное подмножество из n-элементного множества
$(n− 1)$ -элементное подмножество из n-элементного множества
...
$1$ -элементное подмножество из n-элементного множества
$0$ -элементное подмножество из n-элементного множества

То есть мы суммируем количество способов выбрать все возможные подмножества из $n$ -элементного множества. Но таких подмножеств будет ровно $n 2 ,$ поскольку подмножество множества $X$ можно задать так: сопоставить 0 тем элементам, которые в подмножество не входят, и 1 - тем элементам, которые в подмножество входят. Тогда различных подмножеств множества $X$ всего столько же, сколько строк длины $|X |,$ составленных из нулей и единиц, то есть $2n$

d) $(nk)$ при фиксированном $k$ - это количество способов выбрать $k$ объектов из всё бОльших и бОльших множеств ( $n$ растёт по условию, а $n$ - это и есть "размер" $\text{[math]}$ множества, из которого мы выбираем). Таким образом, очевидно, что т.к. растёт количество элементов в множестве, из которого мы выбираем элементы, то и вариантов выбрать какие-то $k$ у нас будет становиться всё больше и больше.

e)* Заметим такое очевидное соотношение:

$(n ) = ----n!-----= ---n!- ⋅--k-- = (n)⋅--k-- k−1 (k−1)!(n−k+1)! k!(n−k)! n−k+1 k n−k+1$

Что же оно нам даёт? А даёт оно нам условие, при котором при фиксированном $n$ предыдущий по $k$ биномиальный коэффициент не больше следующего. А именно, если присмотреться, то из нашей формулы следует, что:

( ) ( ) n ≤ n если и только если---k---- ≤ 1 k− 1 k n − k+ 1

Но это последнее условие уже, в свою очередь, эквивалентно тому, что $k ≤ n− k + 1,$ то есть $2k ≤ n + 1,$ то есть $k ≤ n+1. 2$

Отсюда делаем вывод, что биномиальные коэффициенты растут при фиксированном $n$ до тех пор, пока $k ≤ n+21.$ То есть, наибольшее значение $( ) nk$ будет при максимальном $k$ таком, что $k ≤ n+1. 2$ А это есть просто $k = ⌊n+1⌋ 2$ ( $⌊...⌋$ означает округление вниз до ближайшего целого.)

Ответ:

Нужна консультация? Задайте нам вопрос в чате.

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

.15 Последовательности. Индукция.

Специальные программы

Программалояльности v2.0

Крути рулеткуи выигрывай призы!

Бесплатное онлайн-обучение

Налоговые вычеты

Специальное предложениедля учителей

Вернём деньги за курсза твою сотку на ЕГЭ

Программалояльности v2.0

Крути рулеткуи выигрывай призы!

Бесплатное онлайн-обучение

Налоговые вычеты

Специальное предложениедля учителей

Вернём деньги за курсза твою сотку на ЕГЭ

Программа
лояльности v2.0

Крути рулетку
и выигрывай призы!

Специальное предложение
для учителей

Вернём деньги за курс
за твою сотку на ЕГЭ

Программа
лояльности v2.0

Крути рулетку
и выигрывай призы!

Специальное предложение
для учителей

Вернём деньги за курс
за твою сотку на ЕГЭ