Задача 73804

Темы:    [ Рекуррентные соотношения (прочее) ] [ Целочисленные и целозначные многочлены ] [ Суммы числовых последовательностей и ряды разностей ]

Сложность: 5 Классы: 8,9,10,11 Название задачи: Числа Стирлинга.

Условие

Автор: Ясиновый Э.А.

Обозначим через T_k(n) сумму произведений по k чисел от 1 до n. Например,    T₂(4) = 1·2 + 1·3 + 1·4 + 2·3 + 2·4 + 3·4.
   а) Найдите формулы для T₂(n) и T₃(n).
   б) Докажите, что T_k(n) является многочленом от n степени 2k.
   в) Укажите метод нахождения многочленов T_k(n) при  k = 2, 3, 4, ...  и примените его для отыскания многочленов T₄(n) и T₅(n).

Решение

  а)  2T₂(n) = (1 + ... + n)² – (1² + ... + n²) =

 

   T₃(n) находится аналогично из равенства
      6T₃(n) = (1 + ... + n)³ – 3(1² + ... + n²)(1 + ... + n) + 2(1³ + ... + n³) =

       

(Формулы для сумм квадратов и кубов см. в задачах 60282, 61431.)

  б) Разобьем все слагаемые суммы T_k(n) на две группы: в одну включим те произведения, в которые входит n, в другую – остальные. Отсюда
      T_k(n) – T_k(n–1) = nT_k–1(n–1)    (*).
  Теперь утверждение доказыаается по индукции.
  База.   

  Шаг индукции. По предположению индукции  nT_k–1(n–1)  – многочлен степени  2k – 1  от n. Теперь из задачи 61434 следует, что существует многочлен степени 2k, значения которого совпадает с T_k(n) при всех натуральных n.

 в) Полученная выше рекуррентная формула (*) и очевидное равенство  T_k(k) = k!  позволяют последовательно вычислять многочлены T_k(n): формулу (*) можно рассматривать как систему уравнений на коэффициенты многочлена T_k.
  Чтобы уменьшить число неизвестных, заметим, что значения многочлена T_k имеют смысл не только при натуральных  n ≥ k,  но и при всех целых (и даже действительных) n. Глядя на формулы для T₁, T₂, T₃, разумно предположить, что
      T_k(k–1) = T_k(k–2) = ... = T_k(1) = T_k(0) = T_k(–1) = 0.
Это предположение не противоречит рекуррентной формуле.
  Например, будем искать T₄(n) в виде   (n + 1)n(n – 1)(n – 2)(n – 3)P(n),   где   P(n) = an³ + bn² + cn + d.   Выписав (*) для  k = 4  и сократив на  n(n – 1)(n – 2)(n – 3),  получим
      
или   48(n + 1)(an³ + bn² + cn + d) – 48(n – 4)(a(n – 1)³ + b(n – 1)² + c(n – 1) + d) = n²(n – 1).
  Далее можно приравнять коэффициенты при одинаковых степенях (например, сравнивая коэффициенты при n³, получим
48(a + b + 4a + 3a – b) = 1,  откуда  a = ¹/₃₈₄).
  Или можно подставлять "малые" значения n. Например, при  n = 1  получим соотношение  2a + 2b + 2c + 5d = 0.
  Продолжая таким образом, найдем указанное в ответе выражение для T₄. Аналогично находится T₅.

Ответ

а)   

в)   

      

Замечания

Другой способ вычисления и обсуждение связанных с этим вопросов см. в решениях Задачника "Кванта".

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

журнал
Название	"Квант"
год
Год	1974
выпуск
Номер	6
Задача
Номер	М269