Решение задач по дискретной математике

Задание: Доказать тождество \( C_n^m = C_{n-1}^{m-1} + C_{n-1}^m \). Доказательство: Для доказательства воспользуемся основной формулой числа сочетаний: \[ C_n^k = \frac{n!}{k!(n-k)!} \] Распишем правую часть уравнения: \[ C_{n-1}^{m-1} + C_{n-1}^m = \frac{(n-1)!}{(m-1)!( (n-1)-(m-1) )!} + \frac{(n-1)!}{m!(n-1-m)!} \] Упростим знаменатель в первой дроби: \[ (n-1)-(m-1) = n-1-m+1 = n-m \] Получаем: \[ \frac{(n-1)!}{(m-1)!(n-m)!} + \frac{(n-1)!}{m!(n-m-1)!} \] Чтобы сложить эти дроби, приведем их к общему знаменателю. Заметим, что: 1. \( m! = m \cdot (m-1)! \) 2. \( (n-m)! = (n-m) \cdot (n-m-1)! \) Общим знаменателем будет \( m!(n-m)! \). Домножим первую дробь на \( m \), а вторую на \( (n-m) \): \[ \frac{(n-1)! \cdot m}{m!(n-m)!} + \frac{(n-1)! \cdot (n-m)}{m!(n-m)!} \] Теперь запишем под одной чертой дроби и вынесем общий множитель \( (n-1)! \) за скобки: \[ \frac{(n-1)! \cdot (m + n - m)}{m!(n-m)!} \] В скобках \( m \) и \( -m \) взаимно уничтожаются, остается \( n \): \[ \frac{(n-1)! \cdot n}{m!(n-m)!} \] Так как \( (n-1)! \cdot n = n! \), получаем: \[ \frac{n!}{m!(n-m)!} \] Это выражение в точности соответствует определению \( C_n^m \). Таким образом: \[ C_{n-1}^{m-1} + C_{n-1}^m = C_n^m \] Что и требовалось доказать.