Умножение многочленов и число ненулевых коэффициентов — олимпиадная за

  Докажем утверждение индукцией по n.

  База. При  n = 1  утверждение очевидно.

  Шаг индукции. Рассмотрим произведение  Q(x) = (x + 1)ⁿP(x),  где P(x) – некоторый ненулевой многочлен. Без ограничения общности можно считать, что свободный член многочлена P(x) отличен от нуля (умножение на x не меняет числа ненулевых коэффициентов), тогда у многочлена Q(x) свободный член также отличен от нуля и у производной Q'(x) на один ненулевой коэффициент меньше, чем у Q(x). Но

Q'(x) = (x + 1)ⁿP'(x) + n(x + 1)^n–1P(x) = (x + 1)^n–1((x + 1)P'(x) + nP(x)),  то есть Q'(x) получается домножением многочлена  (x + 1)^n–1  на ненулевой (как легко проверить) многочлен. По предположению индукции у многочлена Q'(x) не менее n ненулевых коэффициентов, следовательно, у многочлена Q(x) не менее

n + 1  ненулевых коэффициентов.

Ответ задачи отсутствует