|
|
 |
Условие
Рассмотрим все возможные наборы чисел из множества {1, 2, 3, ..., n}, не содержащие двух соседних чисел.
Докажите, что сумма квадратов произведений чисел в этих наборах равна (n + 1)! – 1.
Решение
Обозначим искомую сумму через Sn и будем указанное равенство индукцией по n. База: S1 = 1 = (1 + 1)! – 1, S2 = 1² + 2² = 5 = (2 + 1)! – 1.
Шаг индукции. Разобьём указанные наборы на три группы: набор, состоящий из одного числа n (в сумме ему соответствует слагаемое n²), остальные наборы, содержащие число n, (они дадут сумму n²Sn–2, поскольку n – 1 не может входить в такие наборы), и наборы, не содержащие числа n (они дадут сумму Sn–1). Поэтому
Sn = n²Sn–2 + Sn–1 + n² = n²((n – 1)! – 1) + n! – 1 + n² = n·n! + n! – 1 = (n + 1)! – 1.
Замечания
3 балла
