Многочлены Чебышева и рекуррентные соотношения

12

Многочлены Чебышева и рекуррентные соотношения

Широко распростраен взгляд на математика как на человека, беспрерывно занимающется сложнейшим арифметическими вычислениями (в более утонченном варианте — выписывающего и преобразующего длины и сложные формулы). Читательям «Кванта» хорошо известно, что бывают красивая и важная математica «без формул», одноколая истинь в таком взгляде все же есть. Умение взглянуть на формулы с необходимой точки зрения, преобразовывать их, открывать новые, находить связи между ними — важная часть работы математica. В этой статье мы рассмотрим какад любопытных формул, связанных со значением последовательности «многочленов Чебышева» (некоютые из этих формул предлагалось доказать в задаче М488 — «Квант», 1978, № 2), а также общее математическое идеи, которые стоит за ними.

Введение. Две замечательные последовательности многочленов

Многочлены, о которых будет идти речь, встречаются во многих задачах анализа, вычислительной математики, алгебры. Они появились в 1854 году, в работе русского математика Пафнутья Львовича Чебышева в связи с таким вопросом.

Рассмотрим всевозможные многочлены данной степени $n$ со старшим коэффициентом 1; какой из них наименее уklоняется от нуля на отрезке $[-1; 1]$, то есть для каждого многочлена $F_n(x) = x^n + \dots$ величины

$$c_n = \max_{[-1; 1]} |F_n(x)|$$

наименшая?

Оказывается, это $\bar{T}_n(x) = \frac{1}{2^{n-1}} T_n(x)$ — многочлен из левой колонки таблицы 1, деленный на старший коэффициент. Например, среди квадратных трехчленов — это $x^2 - \frac{1}{2}$ (его отклонение от нуля $c_2$ равно $\frac{1}{2}$, а у любого другого квадратного трехчлена $x^2 + px + q$ оно больше); среди кубических многочленов — это $x^3 - \frac{3}{4} x$ (для него $c_3 = \frac{1}{4}$); и вообще отклонение от нуля $c_n = \frac{1}{2^{n-1}}$ многочлена $\bar{T}_n(x)$ меньше, чем у любого другого многочлена $F_n(x) = x^n + \dots$ степени $n.*$).

Таблица 1. Многочлены Чебышева первого и второго рода. Если умножить каждый из многочленов на 2х и вычесть предыдущий (стоящий над ним), получится следующий.

| $n$ | $T_n$ | $U_n$ |
| :— | :— | :— |
| 0 | 1 | 1 |
| 1 | $x$ | $2x$ |
| 2 | $2x^2 - 1$ | $4x^2 - 1$ |
| 3 | $4x^3 - 3x$ | $8x^3 - 4x$ |
| 4 | $8x^4 - 8x^2 + 1$ | $16x^4 - 12x^2 + 1$ |
| 5 | $16x^5 - 20x^3 + 5x$ | $32x^5 - 32x^3 + 6x$ |
| 6 | $32x^6 - 48x^4 + 18x^2 - 1$ | $64x^6 - 80x^4 + 24x^2 - 1$ |
| 7 | $64x^7 - 112x^5 + 56x^3 - 7x$ | . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . в в в в к лырьсъ�съ�съ�съ�съ�съ�съ�съ�съ�с тейпыс тейпыс тейпыс тейпецыс тейпецыс тейпецыс тейпецыс тейпецыс тейпецыс тейпецс тейпецыс тейпецс тейпецс тейпецс нейпецс тейпецс тейпецс тейпецс тейпецс тейпецс тейпецс тейпецс тейпецс тейпецс тейпецс тейпецс тейпецс тейпецс тейпецс тейпецс тейпецс тейпецс тейпецс тейпецс тейп

13

Если же отклонение от нуля изменять иначе — заменить выражение $c_n$ выражением

$$l_n = \sum_{-1}^{1} |F_n(x)| dx,$$

то наименее уклоняющимся от нуля многочлен $n$-й степени со старшим коэффициентом 1 оказывается многочлен $\tilde{U}_n(x) = \frac{1}{2^n} U_n(x)$, где $U_n(x)$ береется из правой колонки таблицы 1: для многочлена $U_n(x)$ величины $l_n$ (голубая площадь на рисунке 1) равна 2; стало быть, для $\tilde{U}_n$ она равна $1/2^{n-1}$; для любого другого многочлена $F_n(x) = x^n + \dots$ она больше (теорема А. Н. Коркина и Е. И. Золотарева).

Эти факты связаны с таким характеристическими свойствами многочленов Чебышева:

1°. Значения многочлена $T_n$ во всех точках экстремума и в концах отрезка [—1; 1] одинаковы по modulo. Площадь каждого из $n+1$ кусочков, ограниченных графиком многочлена $U_n(x) = \frac{1}{n+1} T'_{n+1}(x)$, осью Ox и прямыми $x = \pm 1$, одна и та же (рис. 1).

(Подобными свойствами обладают лишь многочлены, полученные из равенств $y = U_n(x)$ и $y = T_n(x)$ линейной заменой переменных $x$ и $y$.)
Свойство 1° вытекает из основных соотношений

$$2^\circ. T_n(\cos \varphi) = \cos n\varphi, \quad \sin \varphi \cdot U_{n-1}(\cos \varphi) = \sin n\varphi.$$

*) Здесь мы доказываем этого не будем. Элементарное доказательство можно найти в [1] — первой книге из списка литературы в конце статьи.

При $r=1$:
$$y = T_n(x),$$
при $r=2$:
$$y = Q_n(x)$$

При $r=1$:
$$y = U_{n-1}(x),$$
при $r=2$:
$$y = P_{n-1}(x)$$

Рис. 1. Если произчный лист бумаги $0 \leqslant x \leqslant 2\pi r, -r \leqslant y \leqslant r$ с нарисованным на нем графиком $y = r$ cos $nx$ скрутить в цилиндр (диаметра и высоты $2r$) и посмотреть на него сбоку так, чтобы графики на передней и задней половинках совместились, мы увидим график $n$-го многочлена Чебышева первого рода. Эти графики при $n=2,3,4,5$ изображены в верхнем ряду (при выборе масштаба $r=1$ получаются графики $y = T_n(x)$, при $r=2$ — графики $y = Q_n(x)$ — см. упражнение 3). В нижнем ряду под $n$-м многочлен изображена его произvodная, деленная на $n$; это — $(n-1)$-й многочлен Чебышева второго рода; у него все $n$ голубых фигурок имеют одинаковую площадь.

14

В дополнение к тригонометрическим формулам $2^\circ$, которые определяют значения многочленов $T_n$ и $U_n$ при $|x| \leq 1$, для $|x| > 1$ имеются совершенню иные на вид тожества:

$$3^\circ. \quad T_n(x) = \frac{(x + \sqrt{x^2 - 1})^n + (x - \sqrt{x^2 - 1})^n}{2},$$

$$U_n(x) = \frac{(x + \sqrt{x^2 - 1})^{n+1} - (x - \sqrt{x^2 - 1})^{n+1}}{\sqrt{x^2 - 1}}.$$

Корни многочленов $T_n$ и $U_n$ видны из следующей пары тожеств:

$$4^\circ. \quad T_n(x) = 2^{n-1} \left( x - \cos \frac{\pi}{2n} \right) \left( x - \cos \frac{3\pi}{2n} \right) \dots \left( x - \cos \frac{(2n-1)\pi}{2n} \right),$$

$$U_n(x) = 2^n \left( x - \cos \frac{\pi}{n+1} \right) \left( x - \cos \frac{2\pi}{n+1} \right) \dots \left( x - \cos \frac{n\pi}{n+1} \right).$$

Таким образом, корни и точки экстремума многочлена $T_n(x)$ — проекты вершин правлого $4n$-угольника с диаметром $[-1; 1]$ на этот диаметр (рис. 1).

Ниже мы докажем, наряду с другими, соответствия $2^\circ - 4^\circ$ и проиллюстрируем на их примере некоторые важные методы алгебраических преобразований.

За определение многочленов Чебышева можно было принять любую из написанных выше формул, но нам удобнее положить в основу простое рекуррентное соотношение между ними, которое описано в подписи к таблице 1, и вывести из него все формулы.

Ниже мы предложаем иметь дело с многочленами, получающихся из $T_n$ и $U_n$ изменением масштаба (см. рис. 1): $P_n(x) = U_n(x/2)$, $Q_n(x) = 2T_n(x/2)$; ту роль, которую для $T_n$ и $U_n$ играет отрезок $[-1; 1]$, будет играть теперь отрезок $[-2; 2]$. Новые многочлены хорощем тем, что имеют целые коэффициенты, а их старшие коэффициенты равны 1, (Разумеется, формулы перехода, переписанные в «обратном» виде: $P_n(2x) = U_n(x)$, $Q_n(2x) = 2T_n(x)$, — позволяют в любой момент вернуть к многочленам $U_n$ и $T_n$.) Как правило, мы будем, доказывая что-то для $P_n$, предлагать аналогичные свойства $Q_n$ читателю в качестве упражнения. Призываем его вооружиться карандашом и бумагой и продельать подробно все выкладки, причем сначала — для конкретных небольших значений $n = 2, 3, 4, \dots$ (пока все не станет ясным).

Рекуррентные соотношения и индукция

Положим $P_0(x) = 1$, $P_1(x) = x$ и

$$P_{n+1}(x) = x \cdot P_n(x) - P_{n-1}(x).$$

(1)

Выпишем несколько первых членов этой последовательности. Вслед за $P_0(x) = 1$ и $P_1(x) = x$ идут

$$P_2(x) = x^2 - 1,$$

$$P_3(x) = x(x^2 - 1) - x = x^3 - 2x,$$

$$P_4(x) = x(x^3 - 2x) - (x^2 - 1) = x^4 - 3x^2 + 1,$$

$$P_5(x) = x(x^4 - 3x^2 + 1) - (x^3 - 2x) = x^5 - 4x^3 + 3x$$

и т. д. (для многочленов до $P_{12}$ вы можете проверить результаты по таблице 2).

Многочлены $P_n(x)$ возникают в разных ситуациях. Расмотрим, на пример, дроби

$$R_1(x) = x, \quad R_2(x) = x - \frac{1}{x}, \quad R_3(x) = x - \frac{1}{x - \frac{1}{x}},$$

$$R_4(x) = x - \frac{1}{x - \frac{1}{x}}, \quad R_5(x) = x - \frac{1}{x - \frac{1}{x}}, \dots$$

15

Подобные «миногоэтажные» (так называемые цепные) дроби — полезный инструмент для различных задач о приближениях чисел и функций; ими, кстати говоря, тоже занимаются П. Л. Чебышев.

После преобразования получается

$$R_2(x) = \frac{x^2 - 1}{x}, \quad R_3(x) = \frac{x^3 - 2x}{x^2 - 1},$$

$$R_4(x) = \frac{x^4 - 3x^2 + 1}{x^3 - 2x}, \quad R_5(x) = \frac{x^5 - 4x^3 + 3x}{x^4 - 3x^2 + 1},$$

(проверьте!). Мы видим, что числители и знаменатели в стандартной записи этих дробей — как раз многочлены $P_n(x)$.

Другой пример: рассмотрим функцию sin $n\varphi$ и построаемы выражать ее через sin $\varphi$ и многочлен от cos $\varphi$:

$$\sin 2\varphi = 2\sin \varphi \cdot \cos \varphi,$$

$$\sin 3\varphi = \sin \varphi \cdot (4\cos^2 \varphi - 1),$$

$$\sin 4\varphi = \sin \varphi (8\cos^3 \varphi - 4\cos \varphi)$$

(проверьте!). Оказывается, sin $n\varphi = \sin \varphi \cdot P_{n-1}(2\cos \varphi)$ для всех $n \geqslant 1$; другими словами, при sin $\varphi \neq 0$

$$P_n(2\cos \varphi) = \frac{\sin(n+1)\varphi}{\sin \varphi}.$$

Полученные соответствия нетрудно получить с помощью метода математической индукции и формулы (1). Действительно, $R_{n+1}(x) = x - \frac{1}{R_n(x)}$. Поэтому, если предположить, что для некоторого $n$

$$R_n(x) = \frac{P_n(x)}{P_{n-1}(x)},$$

то из соответствия (1) легко получить аналогическое равенство для $n$, увеличенного на 1:

$$R_{n+1}(x) = x - \frac{P_{n-1}(x)}{P_n(x)} = \frac{xP_n(x) - P_{n-1}(x)}{P_n(x)} = \frac{P_{n+1}(x)}{P_n(x)},$$

что и требуется.

Аналогично для синусов: если предположить, что при $k=n-1$ и $k=n$

$$\sin(k+1)\varphi = \sin \varphi \cdot P_k(2\cos \varphi),$$

то из (1) следует

$$\sin \varphi \cdot P_{n+1}(2\cos \varphi) = 2\cos \varphi \cdot \sin \varphi \cdot P_n(2\cos \varphi) - \sin \varphi \cdot P_{n-1}(2\cos \varphi) =$$

$$= 2\cos \varphi \cdot \sin(n+1)\varphi - \sin n\varphi = \sin(n+2)\varphi;$$

мы воспользовались тождеством 2 cos $\alpha$ sin $\beta = \sin(\alpha + \beta) + \sin(\beta - \alpha)$.

16

(Заметим, что мы провели индуктивный переход не от $n$ к $n+1$, как обычно, а от $n-1$ и $n+1$; при этом необходимо отдельно проверить первый два равенства при $n=0$ и $n=1$.)
Упражнения

1. Докажите с помощью индуктивный переход не от $n$ к $n+1$, как обычно, а от $n-1$ и $n+1$; при этом необходимо отдельно проверить первый два равенства при $n=0$ и $n=1$.
   $$P_n(x) = \frac{(x + \sqrt{x^2 - 4})^{n+1} - (x - \sqrt{x^2 - 4})^{n+1}}{2^{n+1}\sqrt{x^2 - 4}}.$$

(Mы еще к нему вернемся.)
2. Докажите, что a) $P_n(2) = n+1$, 6) $P_n(-2) = (-1)^n \cdot (n+1)$. (Сделайте это треящее способами: с помощью (1), а также переходя к пределу в равенстве (2) при $\varphi \rightarrow 0$ и $\varphi \rightarrow \pi$ и в равенстве (3) — при $x \rightarrow \pm 2$.)
3. Рассмотрим последовательность многочленов $Q_0(x), Q_1(x), Q_2(x), \dots$, удовлетворяющего соответствию (1) и начальным условиям $Q_0(x) = 2, Q_1(x) = x$. Выпишите первый 6 многочленов $Q_n(x)$. Докажите тожество.
a) $Q_n(x)/Q_{n-1}(x) = x - \frac{1}{x - \frac{1}{x - \frac{2}{x}}}$ ($n-1$ минут);
b) $2\cos n\varphi = Q_n(2\cos\varphi)$;
b) при $|x| > 2$
$$Q_n(x) = \frac{(x + \sqrt{x^2 - 4})^n + (x - \sqrt{x^2 - 4})^n}{2^n}.$$
4. Докажите, что любая последовательность многочленов $R_0(x), R_1(x), \dots$, удовлетворяющая соответствию (1), выражается через последовательность $(P_n(x))$ по формуле $R_n(x) = R_1(x) \cdot P_{n-1}(x) - R_0(x) \cdot P_{n-2}(x)$.
В частности, $Q_n(x) = xP_{n-1}(x) - 2P_{n-2}(x) = P_n(x) - P_{n-2}(x)$. Выведите отсюда все тожество из упражнения 3.

Корни многочленов и произведение
Многие интересные формулы, в которых участвуют симметричные выражения от $n$ чисел (или букв), оказываются легко обязываными, если эти числа рассматривать как корни неокоторого многочлена степени $n$. Для $n$ чисел $\gamma_k = 2\cos \frac{k\pi}{n+1}$ (где $k=1,2,\dots,n$) таким многочленом служит наш $P_n(x)$. В самом деле, подставляя в (2) вместо $\varphi$ значение $\frac{\pi}{n+1}$, $\frac{2\pi}{n+1}, \dots, \frac{n\pi}{n+1}$, мы видим, что числа $\gamma_k = 2\cos \frac{k\pi}{n+1}$ — корни многочлена $P_n(x)$. Тут нам понадобится следствие из теоремы Безу: если $\gamma$ — корень многочлена $F(x)$, то $F(x)$ делится на $x-\gamma$. (В самом деле, заменив переменную $x$ на $y=x-\gamma$, мы получим многочлен $\tilde{F}(y) = F(x-\gamma)$, у которого есть корень $y=0$, а такой многочлен, оченьindo, делится на $y^*$). Наш многочлен $P_n(x)$ должен делиться на каждый из двухленов $x-\gamma_k$, а значит — и на их произведение; поскольку он имеет степень $n$ и старший коэффициент 1, он просто равен произведению $\prod_{1 < k < n} (x-\gamma_k)$. Итак,
$$P_n(x) = \prod_{1 < k < n} (x-2\cos \frac{k\pi}{n+1}).$$

Упражнение 5. a) Докажите тожество
$$Q_n(x) = \prod_{1 < k < n} (x-2\cos \frac{(2k-1)\pi}{2n}).$$

6. Проверьте его и тожество (4) для $n=2,3,4$ и 5.

*) Подробнее о теореме Безу и разложении на многочленов см. [2].

17

Приведем одно любопытное tejдество, которое вытекает из сопоставления формул (4) и (2).

Вычислим двумя способами $P_{2m}(0)$ при $m > 0$ и приравняем полученные выражения.

С одной стороны, из (2) получаем

$$P_{2m}(0) = P_{2m}\left(2\cos\frac{\pi}{2}\right) = \left(\sin\frac{(2m+1)\pi}{2}\right)/\sin\frac{\pi}{2} = \sin\left(\frac{\pi}{2} + m\pi\right) = (-1)^m$$

С другой стороны, согласно (4),

$$P_{2m}(0) = \prod_{1 \le k \le 2m} \left(-2\cos\frac{k\pi}{2m+1}\right).$$

Заменив каждое $\cos\frac{k\pi}{2m+1}$ при $m+1 \le k \le 2m$ на $\left(-\cos\left(\pi - \frac{k\pi}{2m+1}\right)\right)$, получим

$$P_{2m}(0) = (-1)^m \cdot \left[2^m \cdot \prod_{1 \le k \le m} \cos\frac{k\pi}{2m+1}\right]^2.$$

Но выражение в квадратных скобках положительное, поскольку в произведение входят косинусы только острых углов; поэтому оно равно 1, то есть

$$\prod_{1 \le k \le m} \cos\frac{k\pi}{2m+1} = \frac{1}{2^m}.$$

Приведем красивую «словесную» формулировку (5): при $m > 0$ среднее геометрическое косинусов острых углов, кратных $\frac{\pi}{2m+1}$, равно $\frac{1}{2}$.

Упражнения
6. а) Найдите $P_n(1), P_n(-1), Q_n(1), Q_n(-1)$.

Докажите похожие на (5) равенства:

6. $\prod_{1 \le k \le m} \sin\frac{k\pi}{2m} = \frac{\sqrt{m}}{2^{m-1}}$ ($m \ge 1$);

b) $\prod_{1 \le k \le m} \mathrm{tg}\frac{k\pi}{2m+1} = \sqrt{2m+1}$ ($m \ge 1$);

г) $\prod_{1 \le k \le m} \cos\frac{(2k-1)\pi}{4m} = \frac{\sqrt{2}}{2^m}$ ($m \ge 1$).

7. Выясните, при каких $m$ и $n$

a) многочлен $P_n$ делится на $P_m$;

b) многочлен $Q_n$ делится на $Q_m$.

Производящие функции, степени ряда и коэффициенты

В этом разделе мы познакомим вас с очень плодотворным методом, широко применяемый в самых различных разделах математики — анализе, комбинаторике, теории вероятности, — с методом производающих функции. Этот метод позволяет иногда собрать отдельные члены последовательности, как «кирпич», в одной целостное «здание» и получить информацию сразу об всей последовательности.

Пусть нам дана последовательность $a_0, a_1, a_2, \dots$. Изовем ее производающей функции выражение

$$f(z) = a_0 + a_1z + a_2z^2 + \dots = \sum_{n \ge 0} a_nz^n.$$

Такие выражения математики называют формульными степенями ряда. Эти ряды можно складывать, вычитать и переменная как общие многочлены, можно делить один ряд на другой (если свободный член ряда-делителя отличен от 0), любой ряд можно почленно дифференцировать и интегрировать — и все эти операции можно использовать,

18

Чтобы получить новые последовательности из уже изученных. Часто оказывается возможность из рекуррентного соотношения, который определяна последовательность, найти простую формулу для ее производашей функции, и набор от — из производашей функции извлечь формулу или соотношения для членов последовательности.

Для конечной последовательности $a_0, a_1, a_2, \dots, a_n$ производающей функцией будет многочлен $f(z) = a_0 + a_1z + \dots + a_nz^n$. Например, многочлен $f_n(z) = (1+z)^n$ служит производающей функцией для биомпаульных коэффициентов $C_n^0, C_n^1, \dots, C_n^n$ — членов $n$-й строки треугольника Паскала (таблица 2):

$$\sum_{0 < k < n} C_n^k z^n = (1+z)^n.$$ (6)

Продифференцировав это тожество $k$ раз и заложив затем $z=0$, найдем $C_n^k = n(n-1) \dots (n-k+1)/1 \cdot 2 \cdot \dots \cdot k$.

Раскрывая скобки и выделяя коэффициенты при $z^m$ в очередном тожестве $(1+z)(1+z)^n = (1+z)^{n+1}$, записанном в виде

$$(1+z) \left( \sum_{0 < k < n} C_n^k z^k \right) = \sum_{0 < k < n+1} C_{n+1}^k z^k,$$

получим важное соотношение $C_n^m + C_n^{m-1} = C_{n+1}^m$.

Средние бесконечных последовательностей особенно простую, легко «сворачивающийся» производашую функцию имеет геометрическая прогрессия $b_0=b, b_n=qb_{n-1}$. Заменив в сумме $f(z) = \sum_{n>0} b_n z^n = b + \sum_{n>1} b_n z^n$ каждое $b_n$ на $qb_{n-1}$, получим $f(z) = b + qz \sum_{n>1} b_{n-1} z^{n-1} = b + qzf(z)$, откуда $f(z)(1-qz) = b$, то есть

$$f(z) = \sum_{n>0} b_n z = \frac{b}{1-qz}.$$ (7)

Это, конечно, известная формула для суммы бесконечной геометрической прогрессии (при $|qz|<1$). Но тем же приемом можно получить и производашую функцию для нашей последовательности многочленов $P_n(x)$.

Положим $\Phi(z) = \sum_{n>0} P_n(x) z^n = 1+xz+\sum_{n>2} P_n(x) z^n$. (Здесть $x$ играет роль параметра и ниже мы для краткости вместе $P_n(x), P_{n-1}(x), \dots$ будем писать $P_n, P_{n-1}, \dots$.) Согласно (1), заменим каждое $P_n$ при $n \geqslant 2$ на $xP_{n-1}-P_{n-2}$. Тогда

$$\Phi(z) = 1+xz + \sum_{n>2} xP_{n-1} z^n - \sum_{n>2} P_{n-2} z^n =$$

$$= 1+xz+xz \cdot \sum_{n>2} P_{n-1} z^{n-1} - z^2 \cdot \sum_{n>2} P_{n-2} z^{n-2} =$$

$$= 1+xz+xz(\Phi(z)-1)-z^2\Phi(z).$$

Следовательно, $\Phi(z) \cdot (z^2-xz+1) = 1$ и

$$\Phi(z) = \frac{1}{z^2-xz+1}.$$ (8)

В этой простой формуле скрыта все хитрая последовательность многочленов $P_n$, который мы до сих пор занимались! Отдельные $P_n$, спрятанные в ней, мы «вытащим» двумя разными способами.

1. При $|x|>2$ квадратное уравнение $z^2-xz+1=0$ имеет два корня:

$$u = \frac{x+\sqrt{x^2-4}}{2}, \quad v = \frac{x-\sqrt{x^2-4}}{2}.$$ (9)

Из $z^2-xz+1=(z-u)(z-v)$, учитывая $uv=1$, получим

19

$$\Phi(z) = \frac{1}{(u-z)(v-z)} = \left( \frac{1}{v-z} - \frac{1}{u-z} \right) \frac{1}{u-v} = \left( \frac{u}{1-zu} - \frac{v}{1-zw} \right) \frac{1}{u-v} = \sum_{n \geq 0} \frac{u^{n+1}-v^{n+1}}{u-v} z^n,$$

то есть $P_n(x) = \left( u^{n+1}-v^{n+1} \right) / (u-v)$; это формула (3).

2. Найдем из (8) отдельные коэффициенты каждого многочлена $P_n(x)$. Делается это так:

$$\Phi(z) = \frac{1}{1-(xz-z^2)} = \sum_{k>0} \left( xz-z^2 \right)^k = \sum_{k>0} \left( \sum_{0<j<k} (-1)^j C_k^j x^{k-j} z^{k+j} \right) = \sum_{n>0} z^n \left( \sum_{j} (-1)^j C_{n-j}^j \cdot x^{n-2j} \right)$$

(мы воспользовались формулами суммы бесконечной геометрической прогрессии (7), биома Ньютона (6) и выделили коэффициент при $z^n$, который и есть нужный нам $P_n(x)$). Следовательно,

$$P_n(x) = \sum_{j} (-1)^j C_{n-j}^j x^{n-2j}$$

(например: $P_6(x) = C_6^0 x^6 - C_5^1 x^4 + C_4^2 x^2 - C_3^3 = x^6 - 5x^4 + 6x^2 - 1$).

Конечно, доказать готовые формулы (3) и (10) можно без произвольных функций — самое замечательное, как они возникли, почти сами собой, из короткой формулы (8).

Обоснование всех действия с бесконечными рядами, которые мы производили — а оно, разумеется, необходимо, — можно было бы проверить, либо заметив, что при необходимости по модели числовых значениях $z$ все рассматриваемые ряды сходятся (как (7) при $|z| < 1/|q|$), то есть представляют настоящие функции от $z$, либо проверив, что для определенных формулыально операционный сложения, умножения и т. д. (каждый коэффициент ряда выражается через конечное число других, а $z$ — просто буква!) выполены все обычные законы. Подробнее с методом произвольных функций и степеними рядами можно познакомиться по книгам [3], [4], [6].

Упражнения

8. Рассмотрим последовательность чисел Фибоначчи

$$u_0 = 0, u_1 = 1, u_{n+1} = u_n + u_{n-1}.$$

a) Докажите, что ее произвольная функция равна $\frac{z}{1-z-z^2}$. Выведите отсюда

b) формулу Бинэ

$$u_n = \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right]$$

(другой вывод этой формулы см. в [5]).

b) Докажите также что $u_n = \sum_{j} C_{n-j}^j$.

9. a) Найните произвольную функцию для последовательности многочленов $Q_n(x)$ из упражнения 3 и докажите с ее помощью, что (при $|x| > 2$)

$$Q_n(x) = u^n - v^n,$$

где $u$ и $v$ определяены формулами (9) (в этом заключалось упражнение 3 в)).

6. (Для тех, кто знаком с комплексными числами; см. [1]). Проверьте, что формулы (3) и (3’) при $|x| < 2$ превращаются в формулы (2) и (2’). (Указание. $u = \cos \varphi + i \sin \varphi, v = \cos \varphi - i \sin \varphi$, если $x = 2 \cos \varphi$.) Литература

1. А. М. Яглом и И. М. Яглом. «Незlementарные задачи в элементарном изложении». («Библиотека математического кружка», выпуск 5) (М., Гостехторидат, 1954); задачи 130—134.

2. «Избранные вопросы математики» (факультативный курс 10), раздел «Комплексные числа и многочлены» (М., «Просвещение», 1980).

3. Д. Пойа, Г. Сеге. «Задание и теоремы из анализа» (М., «Нука», 1978).

4. Анира Картан. «Элементарная теория аналитических функций одного и несколько комплексных переменных» (М., «ИЛ», 1963).

5. Н. Н. Воробьев. «Числа Фибоначчи» («Популярные лекции по математике», выпуск 6) (М., «Нука», 1978).

6. Н. Я. Виленкин. «Комбинаторика» (М., «Нука», 1969).

7. В. А. Успенский. «Треугольник Паскала» («Популярные лекции по математике», выпуск 43) (М., «Нука», 1979).