Задача
Пусть an – число решений уравнения x1 + ... + xk = n в целых неотрицательных числах и F(x) – производящая функция последовательности an.
а) Докажите равенства: F(x) = (1 + x + x² + ...)k = (1 – x)–k.
б) Найдите формулу для an, пользуясь задачей 161490.
Решение
а) Пусть bn – число решений уравнения x1 + ... + xk+1 = n в целых неотрицательных числах. Из каждого такого решения (x1, ..., xk+1) можно получить решение (x1, ..., xk+1 + 1) уравнения x1 + ... + xk+1 = n + 1 (*).
Кроме этого, уравнение (*) имеет еще an+1 решений вида (x1, ..., xk, 0). Следовательно, bn+1 – bn = an+1.
Обозначим производящую функцию из условия через Fk(x). Мы фактически доказали, что (1 – x)Fk+1(x) = Fk(x). Поскольку, очевидно,
F1(x) = 1 + x + x² + ... = (1 – x)–1, то Fk(x) = (1 – x)–k. б) Легко видеть, что 
Отсюда 
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь