5. Докажите каждую из формул двумя способами: комбинаторно и алгебраически. a) C-k = Ck; 6) Ch+1 = C + CK-1. n n

Сnk показывает количество способов выбрать k элементов из n. Каждый раз, когда мы выбираем k элементов, мы также определяем n − k элементов, которые мы не выбрали. Таким образом, количество способов выбрать k элементов равно количеству способов не выбрать n − k элементов. Сkn показывает количество способов выбрать n − k элементов из n. Следовательно, Сnk = Ckn .

Используем формулу для сочетаний: Сnk = n!/k!(n−k)! и Сkn = n!/(n−k)!(n−(n−k))!=n!/(n−k)!k!. Видим, что оба выражения равны.

Рассмотрим группу из n+1 элементов. Выбор k элементов из n+1 можно разделить на два случая: когда выбран конкретный элемент (назовем его А) и когда он не выбран.

• Если элемент А выбран, то нам нужно выбрать k-1 элементов из оставшихся n элементов, что можно сделать Cnk−1 способами.
• Если элемент А не выбран, то нам нужно выбрать k элементов из оставшихся n элементов, что можно сделать Cnk способами.

Следовательно, общее количество способов выбрать k элементов из n+1 равно сумме этих двух случаев: Cn+1k = Cnk + Cn k−1.

Используем формулу сочетаний:Cn+1k = (n+1)!/k!(n+1−k)! Cnk = n!/k!(n−k)! Cn k−1 = n!/(k−1)!(n−k+1)!Подставим в правую часть уравнения: n!/k!(n−k)! + n!/(k−1)!(n−k+1)!=n!(n−k+1)+n!k/k!(n−k+1)!= n!(n+1)/k!(n−k+1)!=(n+1)!/k!(n+1−k)! Получили левую часть уравнения.