Задача 61493

Темы:    [ Производящие функции ] [ Уравнения в целых числах ] [ Треугольник Паскаля и бином Ньютона ]

Сложность: 4- Классы: 8,9,10,11

Условие

Пусть a_n – число решений уравнения  x₁ + ... + x_k = n   в целых неотрицательных числах и F(x) – производящая функция последовательности a_n.
  а) Докажите равенства:  F(x) = (1 + x + x² + ...)^k = (1 – x)^–k.
  б) Найдите формулу для a_n, пользуясь задачей 61490.

Решение

  а) Пусть b_n – число решений уравнения  x₁ + ... + x_k+1 = n  в целых неотрицательных числах. Из каждого такого решения  (x₁, ..., x_k+1)  можно получить решение  (x₁, ..., x_k+1 + 1)  уравнения  x₁ + ... + x_k+1 = n + 1   (*).
  Кроме этого, уравнение (*) имеет еще a_n+1 решений вида  (x₁, ..., x_k, 0).  Следовательно,  b_n+1 – b_n = a_n+1.
  Обозначим производящую функцию из условия через F_k(x). Мы фактически доказали, что  (1 – x)F_k+1(x) = F_k(x).  Поскольку, очевидно,
F₁(x) = 1 + x + x² + ... = (1 – x)^–1,  то  F_k(x) = (1 – x)^–k.

   б) Легко видеть, что     Отсюда  

Замечания

См. также задачу 30719 б).

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	11
Название	Последовательности и ряды
Тема	Последовательности
параграф
Номер	3
Название	Производящие функции
Тема	Производящие функции
задача
Номер	11.067
книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	11
Название	Последовательности и ряды
Тема	Последовательности
параграф
Номер	3
Название	Производящие функции
Тема	Производящие функции
задача
Номер	11.066