2019-01-20
Даны непостоянные многочлены $P(x)$ и $Q(x)$, у которых старшие коэффициенты равны 1. Докажите, что сумма квадратов коэффициентов многочлена $P(x)Q(x)$ не меньше суммы квадратов свободных членов $P(x)$ и $Q(x)$.
Решение:
Рассмотрим произвольный многочлен
$R(x) = c_nx^n + c_{n-1}x^{n-1} + \cdots + c_1x + c_0$.
Назовем его нормой число $|| \mathbb{R}|| = \sqrt{c_n^2 + c_{n-1}^2 + \cdots + c_0^2}$. Положим $R*(x) = c_0x^n + c_1x^{n-1} + \cdots + c_{n-1}x + c_n$.
Лемма. Для любых многочленов $P(x)$ и $Q(x)$ справедливо равенство $||PQ|| = ||PQ*||$.
Доказательство. Пусть $P(x) = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0, Q(x) = b_mx^m + b_{m-1}x^{m-1} + \cdots + b_1x + b_0$. Перемножим многочлены $P(x)$ и $Q(x)$, не приводя подобные члены, и запишем получившиеся коэффициенты (при степенях переменной) в таблицу следующим образом:
Для того чтобы найти коэффициент при $x^k$ в многочлене $P(x)Q(x)$, нужно сосчитать сумму всех чисел, стоящих на соответствующей диагонали
таблицы (на рисунке эти диагонали отмечены сплошными стрелками; будем называть их левыми). Следовательно, квадрат нормы многочлена $P(x)Q(x)$ равен сумме квадратов всех таких сумм.
Перемножив, не приводя подобных членов, многочлены $P(x)$ и $Q*(x)$, записав аналогичным образом получившиеся коэффициенты в таблицу, убеждаемся, что $i$-я строка этой новой таблицы есть $i$-я строка исходной таблицы, элементы которой записаны в обратном порядке: первый элемент стал последним, второй - предпоследним и т. д. Поэтому для того чтобы найти квадрат нормы многочлена $P(x)Q*(x)$, нужно сначала сосчитать сумму всех чисел, стоящих на каждой диагонали таблицы, отмеченной пунктиром (назовем эти диагонали правыми), а затем найти сумму квадратов всех получившихся сумм. Ясно, что в выражении для квадратов норм $||PQ||^2$ и $||PQ*||^2$ квадрат каждого элемента таблицы входит ровно один раз. Покажем, что если удвоенное произведение некоторых двух элементов таблицы входит в выражение для $||PQ||^2$, то оно входит и в выражение для $||PQ*||^2$, и наоборот.
Действительно, рассмотрим элементы $a_xb_y$ и $a_ub_v$, которые стоят на одной и той же левой диагонали таблицы (тогда $x + у = u + v$) и удвоенное произведение которых входит в выражение для $||PQ||^2$. Их удвоенное произведение $2a_xb_ya_ub_v$ входит, соответственно, в выражение для $||PQ*||^2$ как удвоенное произведение элементов $a_xb_v$ и $a_ub_y$, стоящих на одной правой диагонали таблицы (поскольку $x - v = u - у$; более того, все четыре элемента $a_xb_y, a_ub_v, a_xb_v, a_ub_y$ расположены в вершинах прямоугольной подтаблицы исходной таблицы). Лемма доказана.
Рассмотрим теперь многочлены $P(x) = x^n + a_{n-1}x^{n-1} + \cdots + a_1x + + a_0$ и $Q(x) = x^m + b_{m-1}x^{m-1} + \cdots + b_1x + b_0$, старшие коэффициенты которых равны 1. По лемме $||PQ|| = ||PQ*||, Q*(x) = b_0x^m + b_1x^{m-1} + \cdots + b_{m-1}x + 1$. Поэтому $PQ*(x) = b_0x^{m+n} + \cdots + (a_1 + a_0b_{m-1})x + a_0$ и, значит, $||PQ*||^2 \geq a_0 + b_0$. Следовательно, $||PQ||^2 \geq a_0^2 + b_0^2$.