Многочлены Чебышева и рекуррентные соотношенияВасильев Н. Б., Зелевинский А. В. Многочлены Чебышева и рекуррентные соотношения // Квант. — 1982. — № 1. — С. 12—19.
Текст статьиВасильев Н. Б., Зелевинский А. В. Многочлены Чебышева и рекуррентные соотношения // Квант. — 1982. — № 1. — С. 12—19.
Широко распространён взгляд на математика как на человека,
беспрерывно занимающегося сложнейшими арифметическими вычислениями (в более
утончённом варианте — выписывающего и преобразующего длинные и сложные
формулы). Читателям «Кванта» хорошо известно, что бывает красивая и важная
математика «без формул», однако доля истины в таком взгляде всё же есть.
Умение взглянуть на формулы с неожиданной точки зрения, преобразовывать их, открывать новые, находить связи между ними — важная часть работы математика.
В этой статье мы рассмотрим каскад любопытных формул, связанных со знаменитой последовательностью «многочленов Чебышева» (некоторые из этих
формул предлагалось доказать в задаче М488 —
«Квант», 1978, № 2), а также общие математические идеи, которые стоят за ними.
Введение. Две замечательные последовательности многочленов
Многочлены, о которых будет идти речь, встречаются во многих задачах
анализа, вычислительной математики, алгебры. Они появились в 1854 году,
в работе русского математика Пафнутия Львовича Чебышева в связи с таким вопросом.
Рассмотрим всевозможные многочлены данной степени л со старшим
коэффициентом 1; какой из них наименее уклоняется от нуля на отрезке $[-1;1]$, т. е. для какого многочлена $F_n(x)=x^n+\ldots$ величина
$$
c_n=\max\limits_{[-1;1]}|F_n(x)|
$$
наименьшая?
Оказывается, это $\tilde T_n(x)=\dfrac1{2^{n-1}}T_n(x)$ — многочлен из левой колонки таблицы 1, делённый на старший коэффициент. Например,
среди квадратных трёхчленов — это $x^2-\dfrac12$ (его отклонение от нуля$c_2$ равно $\dfrac12$, а у любого другого квадратного трёхчлена
$x^2+px+1$ оно больше); среди кубических многочленов — это $x^3-\dfrac34x$
(для него $c_3=\dfrac14$); и вообще отклонение от нуля $c_n=\dfrac1{2^{n-1}}$
многочлена $\tilde T_n(x)$ меньше, чем у любого другого многочлена
$F_n(x)=x^n+\ldots$ степени $n$.
$
\begin{array}{c|l|l}
n&T_n&U_n\vphantom{\dfrac00}\\\hline\\[-6pt]
0&1&1\\
1&x&2x\\
2&2x^2-1&4x^2-1\\
3&4x^3-3x&8x^3-4x\\
4&8x^3-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&.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.\\
&.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.\\
\end{array}
$
Таблица 1. Многочлены Чебышева первого и второго
рода. Если умножить каждый из многочленов на $2x$ и вычесть предыдущий
(стоящий над ним), получится следующий.
Если же отклонение от нуля измерять иначе — заменить выражение $c_n$
выражением
$$
l_n=\textstyle\int\limits_{-1}^1|F_n(x)|\,dx,
$$
то наименее уклоняющимся от нуля многочленом $n$-й степени со старшим
коэффициентом 1 окажется многочлен $\tilde U_n(x)=\dfrac1{2^n}U_n(x)$, где $U_n(x)$ берётся из правой колонки таблицы 1: для многочлена $U_n(x)$
величина $l_n$ (голубая площадь на рисунке 1) равна 2; стало быть, для $\tilde U_n$ она равна $\dfrac1{2^{n-1}}$; для любого другого многочлена
$F_n(x)=x^n+\ldots$ она больше (теорема А. Н. Коркина и Е. И. Золотарёва).
Эти факты связаны с такими характеристическими свойствами многочленов
Чебышева:
1°.Значения многочлена $T_n$ во всех точках экстремума и в концах отрезка $[-1;1]$ одинаковы по модулю. Площадь каждого из $n+1$
кусочков, ограниченных графиком многочлена $U_n(x)=\dfrac1{n+1}T_{n+1}'(x)$,
осью $Ox$ и прямыми $x=\pm1$, одна и та же (рис. 1).
(Подобными свойствами обладают лишь многочлены, полученные из равенств
$y=U_n(x)$ и $y=T_n(x)$ линейной заменой переменных $x$ и $y$.)
3°. В дополнение к тригонометрическим формулам 2°, которые
определяют значения многочленов $T_n$ и $U_n$ при $|x|\le1$, для $|x|\gt1$
имеются совершенно иные на вид тождества:
$$
\begin{gathered}
T_n(x)=\dfrac{(x+\sqrt{x^2-1})^n+(x-\sqrt{x^2-1})^n}2,\\
Q_n(x)=\dfrac{(x+\sqrt{x^2-1})^{n+1}-(x-\sqrt{x^2-1})^{n+1}}{\sqrt{x^2-1}},\\
\end{gathered}
$$
4°. Корни многочленов $T_n$ и $U_n$ видны из следующей пары
тождеств:
$$
\begin{aligned}
T_n(x)&=2^{n-1}\left(x-\cos\dfrac\pi{2n}\right)
\left(x-\cos\dfrac{3\pi}{2n}\right)\ldots
\left(x-\cos\dfrac{(2n-1)\pi}{2n}\right),\\
Q_n(x)&=2^n\left(x-\cos\dfrac\pi{n+1}\right)
\left(x-\cos\dfrac{2\pi}{n+1}\right)\ldots
\left(x-\cos\dfrac{n\pi}{n+1}\right).
\end{aligned}
$$
Таким образом, корни и точки экстремума многочлена $T_n(x)$ — проекции
вершин правильного $n$-угольника с диаметром $[-1;1]$ на этот диаметр
(рис. 1).
Рис. 1.
Если прозрачный лист бумаги $0\le x\le2\pi r$, $-r\le y\le 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$-м многочленом
изображена его производная, делённая на $n$; это — $(n-1)$-й многочлен
Чебышева второго рода; у него все $n$ голубых фигурок имеют одинаковую
площадь.
Ниже мы докажем, наряду с другими, соотношения 2°—4° и проиллюстрируем на их примере некоторые важные методы алгебраических
преобразований.
За определение многочленов Чебышева можно было бы принять любую
из написанных выше формул, но нам удобнее положить в основу простое
рекуррентное соотношение между ними, которое описано в подписи к таблице 1, и вывести из него все формулы.
Ниже мы предпочитаем иметь дело с многочленами,
получающимися из $T_n$ и $U_n$ изменением масштаба (см. рис. 1):
$P_n(x)=U_n{\left(\dfrac x2\right)}$, $Q_n(x)=2T_n{\left(\dfrac x2\right)}$;
ту роль, которую для $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, $\ldots$ (пока всё не станет ясным).
Рекуррентные соотношения и индукция
Положим $P_0(x)=1$, $P_1(x)=x$ и $$
P_{n+1}(x)=x\cdot P_n(x)-P_{n-1}(x).\tag1
$$
Выпишем несколько первых членов этой последовательности. Вслед за $P_0(x)=1$ и $P_1(x)=x$ идут
$$
\begin{aligned}
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
\end{aligned}
$$
и т. д. (для многочленов до $P_{12}$ вы можете проверить результаты по таблице 2).
Таблица 2. Треугольник Паскаля. О свойствах биномиальных
коэффициентов, составляющих этот треугольник, подробно рассказано в брошюре
[7]. Числа, стоящие на $n$-й красной диагонали, взятые с чередующимися
знаками, — коэффициенты многочленов $P_n(x)$; про их сумму — со знаками и без — см. упражнения 6а) и 8в).
Многочлены $P_n(x)$ возникают в разных ситуациях. Рассмотрим, например,
дроби
$$
\begin{gathered}
R_1(x)=x,\quad R_2(x)=x-\dfrac1x,\quad R_3(x)=x-\dfrac1{x-\dfrac1x},\\
R_4(x)=x-\dfrac1{x-\dfrac1{x-\dfrac1x}},\quad
R_5(x)=x-\dfrac1{x-\dfrac1{x-\dfrac1{x-\dfrac1x}}},\quad\ldots
\end{gathered}
$$
Подобные «многоэтажные» (так называемые цепные) дроби — полезный
инструмент для различных задач о приближениях чисел и функций; ими, кстати
говоря, тоже занимался П. Л. Чебышев.
После преобразований получается
$$
\begin{gathered}
R_2(x)=\dfrac{x^2-1}x,\quad R_3(x)=\dfrac{x^3-2x}{x^2-1},\\
R_4(x)=\dfrac{x^4-3x^2+1}{x^3-2x},\quad
R_5(x)=\dfrac{x^5-4x^3+3x}{x^4-3x^2+1},\quad\ldots
\end{gathered}
$$
(проверьте!). Мы видим, что числители и знаменатели в стандартной записи
этих дробей — как раз многочлены $P_n(x)$.
Другой пример: рассмотрим функцию $\sin n\phi$ и постараемся выразить её через $\sin\phi$ и многочлен от $\cos\phi$:
$$
\begin{aligned}
\sin2\phi&=\sin\phi\cdot2\cos\phi,\\
\sin3\phi&=\sin\phi\cdot(4\cos^2\phi-1),\\
\sin4\phi&=\sin\phi\cdot(8\cos^3\phi-4\cos\phi)
\end{aligned}
$$
(проверьте!). Оказывается, $\sin n\phi=\sin\phi\cdot P_{n-1}(2\cos\phi)$ для всех $n\ge1$; другими словами, при $\sin\phi\ne0$
$$
P_n(2\cos\phi)=\dfrac{\sin{(n+1)\phi}}{\sin\phi}.\tag2
$$
Полученные соотношения нетрудно получить с помощью метода
математической индукции и формулы (1). Действительно,
$R_{n+1}(x)=x-\dfrac1{R_n(x)}$. Поэтому, если предположить, что для некоторого $n$
$$
R_n(x)=\dfrac{P_n(x)}{P_{n-1}(x)},
$$
то из соотношения (1) легко получить аналогичное равенство для $n$,
увеличенного на 1:
$$
R_{n+1}(x)=x-\dfrac{P_{n-1}(x)}{P_n(x)}=\dfrac{xP_n(x)-P_{n-1}(x)}{P_n(x)}=
\dfrac{P_{n+1}(x)}{P_n(x)},
$$
что и требуется.
Аналогично для синусов: если предположить, что при $k=n-1$ и $k=n$
$$
\sin{(k+1)\phi}=\sin\phi\cdot P_n(2\cos\phi),
$$
то из (1) следует
$$
\begin{gathered}
\sin\phi\cdot P_{n+1}(2\cos\phi)=2\cos\phi\cdot\sin\phi\cdot P_n(2\cos\phi)-
\sin\phi\cdot P_{n-1}(2\cos\phi)=\qquad\\
\qquad=2\cos\phi\cdot\sin{(n+1)\phi}-\sin n\phi=\sin{(n+2)\phi};
\end{gathered}
$$
мы воспользовались тождеством
$2\cos\alpha\sin\beta=\sin(\alpha+\beta)+\sin(\beta-\alpha)$.
(Заметим, что мы провели индуктивный переход не от $n$ к $n+1$, как обычно, а от $n-1$ и $n$ к $n+1$, при этом необходимо отдельно
проверить первые два равенства при $n=0$ и $n=1$.)
Упражнения
Докажите с помощью индукции и рекуррентного соотношения (1), что при $|x|\gt2$ справедливо тождество
$$
P_n(x)=\dfrac{(x+\sqrt{x^2-4})^{n+1}-(x-\sqrt{x^2-4})^{n+1}}{2^{n+1}\,
\sqrt{x^2-4}}.\tag3
$$
(Мы ещё к нему вернёмся.)
Докажите, что
$P_n(2)=n+1$;
$P_n(-2)=(-1)^n\cdot(n+1)$.
(Сделайте это тремя способами: с помощью (1), а также переходя к пределу в равенстве (2) при $\phi\to0$ и в равенстве (3) — при $x\to\pm2$.)
при $|x|\gt2$
$$
Q_n(x)=\dfrac{(x+\sqrt{x^2-4})^n+(x-\sqrt{x^2-4})^n}{2^n}.\tag{3′}
$$
Докажите, что любая последовательность многочленов $R_0(x)$, $R_1(x)$,
$\ldots$, удовлетворяющая соотношению (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\dfrac{k\pi}{n+1}$ (где $k=1$, 2, $\ldots$, $n$) таким
многочленом служит наш $P_n(x)$. В самом деле, подставляя в (2) вместо
$\phi$ значения $\dfrac\pi{n+1}$, $\dfrac{2\pi}{n+1}$, $\ldots$,
$\dfrac{n\pi}{n+1}$, мы видим, что числа $\gamma_k=2\cos\dfrac{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$, а такой многочлен, очевидно, делится на $y$.) Наш многочлен $P_n(x)$ должен делиться на каждый из двучленов $x-\gamma_k$, а значит — и на их произведение; поскольку он имеет степень $n$ и старший
коэффициент 1, он просто равен произведению
$\prod\limits_{1\le k\le n}(x-\gamma_k)$. Итак,
$$
P_n(x)=\prod\limits_{1\le k\le n}\left(x-2\cos\dfrac{k\pi}{n+1}\right).\tag4
$$
Проверьте его и тождество (4) для $n=2$, 3, 4 и 5.
Приведём одно любопытное тождество, которое вытекает из сопоставления
формул (4) и (2).
Вычислим двумя способами $P_{2m}(0)$ при $m\gt0$ и приравняем полученные
выражения.
С одной стороны, из (2) получаем
$$
P_{2m}(0)=P_{2m}{\left(2\cos\dfrac\pi2\right)}=\dfrac{\sin\dfrac{(2m+1)\pi}2}
{\sin\dfrac\pi2}=\sin\left(\dfrac\pi2+m\pi\right)=(-1)^m.
$$
С другой стороны, согласно (4),
$$
P_{2m}(0)=\prod\limits_{1\le k\le2m}\left(-2\cos\dfrac{k\pi}{2m+1}\right).
$$
Заменив каждое $\cos\dfrac{k\pi}{2m+1}$ при $m+1\le k\le2m$ на $\left(-\cos\left(\pi-\dfrac{k\pi}{2m+1}\right)\right)$, получим
$$
P_{2m}(0)=(-1)^m\cdot\left[2^m\cdot\prod\limits_{1\le k\le m}\cos\dfrac{k\pi}
{2m+1}\right]^2.
$$
Ho выражение в квадратных скобках положительно, поскольку в произведение
входят косинусы только острых углов; поэтому оно равно 1, т. е.
$$
\prod\limits_{1\le k\le m}\cos\dfrac{k\pi}{2m+1}=\dfrac1{2^m}.\tag5
$$
Приведём красивую «словесную» формулировку (5): при $m\gt0$ среднее
геометрическое косинусов острых углов, кратных $\dfrac\pi{2m+1}$, равно
$\dfrac12$.
Производящие функции, степенные ряды и коэффициенты
В этом разделе мы познакомим вас с очень плодотворным методом, широко
применяемым в самых различных разделах математики — анализе, комбинаторике,
теории вероятностей, — с методом производящих функций. Этот метод
позволяет иногда собрать отдельные члены последовательности, как «кирпичи»,
в одно целостное «здание» и получить информацию сразу обо всей
последовательности.
Пусть нам дана последовательность $a_0$, $a_1$, $a_2$, $\ldots$ Назовём
её производящей функцией выражение
$$
f(x)=a_0+a_1z+a_2z^2+\ldots=\textstyle\sum\limits_{n\ge0}a_nz^n.
$$
Такие выражения математики называют формальными степенными рядами.
Эти ряды можно складывать, вычитать и перемножать как обычные многочлены,
можно делить один ряд на другой (если свободный член ряда-делителя отличен
от 0), любой ряд можно почленно дифференцировать и интегрировать — и все эти операции можно использовать, чтобы получать новые последовательности из уже изученных. Часто оказывается возможным из рекуррентного соотношения, которым
определена последовательность, найти простую формулу для её производящей
функции, и наоборот — из производящей функции извлечь формулу или соотношения для членов последовательности.
Для конечной последовательности $a_0$, $a_1$, $a_2$, $\ldots$, $a_n$
производящей функцией будет многочлен $f(z)=a_0+a_1z+\ldots+a_nz^n$.
Например, многочлен $f_n(z)=(1+z)^n$ служит производящей функцией для биномиальных коэффициентов$C_n^0$, $C_n^1$, $\ldots$, $C_n^n$ —
членов $n$-й строки треугольника Паскаля (таблица 2):
$$
\textstyle\sum\limits_{0\le k\le n}C_n^kz^k=(1+z)^n.\tag6
$$
Продифференцировав это тождество $k$ раз и заложив затем $z=0$, найдём
$C_n^k=\dfrac{n(n-1)\ldots(n-k+1)}{1\cdot2\cdot\ldots\cdot k}$.
Раскрывая скобки и выделяя коэффициенты при $z^m$ в очевидном тождестве
$(1+z)(1+z)^n=(1+z)^{n+1}$, записанном в виде
$$
\textstyle(1+z)\left(\sum\limits_{0\le k\le n}C_n^kz^k\right)=\sum\limits
_{0\le k\le n+1}C_{n+1}^kz^k,
$$
получим важное соотношение $C_n^m+C_n^{m-1}=C_{n+1}^m$.
Среди бесконечных последовательностей особенно простую, легко
«сворачивающуюся» производящую функцию имеет геометрическая прогрессия
$b_0=b$, $b_n=qb_{n-1}$. Заменив в сумме
$$
\textstyle f(z)=\sum\limits_{n\ge0}b_nz^n=b+\sum\limits_{n\ge1}b_nz^n
$$
каждое $b_n$ на $qb_{n-1}$, получим
$$
\textstyle f(z)=b+qz\sum\limits_{n\ge1}b_{n-1}z^{n-1}=b+qz\,f(z),
$$
откуда $f(z)\,(1-qz)=b$, т. е.
$$
\textstyle f(z)=\sum\limits_{n\ge0}b_nz^n=\dfrac b{1-qz}.\tag7
$$
Это, конечно, известная формула для суммы бесконечной геометрической
прогрессии (при $|qz|\lt1$). Но тем же приёмом можно получить и производящую
функцию для нашей последовательности многочленов $P_n(x)$.
Положим
$$
\textstyle\mathit{\Phi}(z)=\sum\limits_{n\ge0}P_n(x)\,z^n=1+xz+\sum\limits
_{n\ge2}P_n(x)\,z^n.
$$
(Здесь $x$ играет роль параметра и ниже мы для краткости вместо $P_n(x)$,
$P_{n-1}(x)$, $\ldots$ будем писать $P_n$, $P_{n-1}$, $\ldots$) Согласно
(1), заменим каждое $P_n$ при $n\ge2$ нa $xP_{n-1}-P_{n-2}$. Тогда
$$
\begin{gathered}
\textstyle\mathit{\Phi}(z)=1+xz+\sum\limits_{n\ge2}xP_{n-1}z^n-
\sum\limits_{n\ge2}P_{n-2}z^n=\qquad\\
\textstyle=1+xz+xz\cdot\sum\limits_{n\ge2}P_{n-1}z^{n-1}-z^2\cdot
\sum\limits_{n\ge2}P_{n-2}z^{n-2}=\\
\qquad\textstyle=1+xz+xz(\mathit{\Phi}(z)-1)-z^2\,\mathit{\Phi}(z).
\end{gathered}
$$
Следовательно, $\mathit{\Phi}(z)\cdot(z^2-xz+1)=1$ и $$
\mathit{\Phi}(z)=\dfrac1{z^2-xz+1}.\tag8
$$
В этой простой формуле скрыта вся хитрая последовательность многочленов
$P_n$, которой мы до сих пор занимались! Отдельные $P_n$, спрятанные в ней,
мы «вытащим» двумя разными способами.
1) При $|x|\gt2$ квадратное уравнение $z^2-xz+1=0$ имеет два корня:
$$
u=\dfrac{x+\sqrt{x^2-4}}2,\quad v=\dfrac{x-\sqrt{x^2-4}}2.\tag9
$$
Из $z^z-xz+1=(z-u)(z-v)$, учитывая $uv=1$, получим
$$
\begin{aligned}
\mathit{\Phi}(z)&=\dfrac1{(u-z)(v-z)}=\left(\dfrac1{v-z}-\dfrac1{u-z}\right)
\dfrac1{u-v}=\\
&=\left(\dfrac u{1-zu}-\dfrac v{1-zv}\right)\dfrac1{u-v}=
\sum\limits_{n\ge0}\dfrac{u^{n+1}-v^{n+1}}{u-v}z^n,
\end{aligned}
$$
т. е. $P_n(x)=\dfrac{u^{n+1}-v^{n+1}}{u-v}$; это формула (3).
2) Найдём из (8) отдельные коэффициенты каждого многочлена $P_n(x)$.
Делается это так:
$$
\begin{gathered}
\mathit{\Phi}(z)=\dfrac1{1-(xz-z^2)}=\textstyle\sum\limits_{k\ge0}(xz-z^2)^k=
\sum\limits_{k\ge0}\left(\sum\limits_{0\le j\le k}(-1)^jC_k^jx^{k-j}z^{k+j}
\right)=\\
\textstyle=\sum\limits_{n\ge0}z^n\left(\sum\limits_j(-1)^jC_{n-j}^j
x^{n-2j}\right)
\end{gathered}
$$
(мы воспользовались формулами суммы бесконечной геометрической прогрессии
(7), бинома Ньютона (6) и выделили коэффициент при $z^n$, который и есть
нужный нам $P_n(x)$). Следовательно,
$$
\textstyle P_n(x)=\sum\limits_j{(-1)^j}C_{n-j}^jx^{n-2j}\tag{10}
$$
(например: $P_6(x)=C_6^0x^6-C_5^1x^4+C_4^2x^2-C_3^3=x^6-5x^4+6x^2-1$).
Конечно, доказать готовые формулы (3) и (10) можно без производящих функций — самое замечательное, как они возникли, почти сами
собой, из короткой формулы (8).
Обоснование всех действий с бесконечными рядами, которые мы производили — а оно, разумеется, необходимо, — можно было бы провести, либо
заметив, что при небольших по модулю числовых значениях $z$ все рассматриваемые ряды сходятся (как (7) при $|z|\lt\dfrac1{|q|}$), т. е.
представляют настоящие функции от $z$, либо проверив, что для определённых
формально операций сложения, умножения и т. д. (каждый коэффициент ряда
выражается через конечное число других, а $z$ — просто буква!) выполнены все обычные законы. Подробнее с методом производящих функций и степенными рядами
можно познакомиться по книгам [3], [4], [6].
Упражнения
Рассмотрим последовательность чисел Фибоначчи
$$
u_0=0,\quad u_1=1,\quad u_{n+1}=u_n+u_{n-1}.
$$
Докажите, что её производящая функция равна $\dfrac z{1-z-z^2}$.
Выведите отсюда формулу Бинэ
$$
u_n=\dfrac1{\sqrt5}\left[\left(\dfrac{1+\sqrt5}2\right)^n-
\left(\dfrac{1-\sqrt5}2\right)^n\right]
$$
(другой вывод этой формулы см. в [5]).
Найдите производящую функцию для последовательности многочленов $Q_n(x)$ из упражнения 3 и докажите с её помощью, что (при $|x|\gt2$)
$$
Q_n(x)=u^n-v^n,
$$
где $u$ и $v$ определены формулами (9) (в этом заключалось
упражнение 3в)).
(Для тех, кто знаком с комплексными числами; см. [1].) Проверьте, что формулы (3) и (3′) при $|x|\lt2$ превращаются в формулы (2) и (2′).
(Указание.$u=\cos\phi+i\sin\phi$, $v=\cos\phi-i\sin\phi$, если
$x=2\cos\phi$.)
Литература
А. М. Яглом и И. М. Яглом. Неэлементарные задачи в элементарном
изложении. — («Библиотека математического кружка»; выпуск 5). — M.:
Гостехтеориздат, 1954. — Задачи 130—134.
Избранные вопросы математики (факультативный курс 10). — М.:
Просвещение, 1980. — Раздел «Комплексные числа и многочлены».
Д. Пойа, Г. Сегё. Задачи и теоремы из анализа. — М.: Наука, 1978.
Анри Картан. Элементарная теория аналитических функций одного и нескольких комплексных переменных. — M.: ИЛ, 1963.
Н. Н. Воробьёв. Числа Фибоначчи. — («Популярные лекции по математике»; выпуск 6). — М.: Наука, 1978.
Н. Я. Виленкин. Комбинаторика. — М.: Наука, 1969.
В. А. Успенский. Треугольник Паскаля. — («Популярные лекции по математике»; выпуск 43). — М.: Наука, 1979.
![{ls}Таблица 2.{/ls} Треугольник Паскаля. О свойствах биномиальных коэффициентов, составляющих этот треугольник, подробно рассказано в брошюре [7]. Числа, стоящие на <nowrap>{literal}$n${/literal}</nowrap>-й красной диагонали, взятые с чередующимися знаками, — коэффициенты многочленов <nowrap>{literal}$P n(x)${/literal};</nowrap> про их сумму — со знаками и без — см. упражнения 6а) и 8в).](http://www.kvant.digital/media/1982-01-015-02.png?_v=2)