Метод спуска, индукция и последовательное конструирование в ТЧ

(a) Будем доказывать индукцией по числу

Проверим базу. При выражение имеет вид — это многочлен нужного вида.

Пусть для любого набора и некоторого числа утверждение задачи верно. Докажем, что оно верно и для числа с любым набором

По индуктивному предположению имеем:

Осталось доказать, что представим в виде многочлена от Рассмотрим случая:

1.

Пусть — нечетное число. Тогда получаем

По индуктивному предположению получаем:

Это тоже многочлен вида Очевидно, сумма многочленов такого вида есть многочлен такого вида.

2.

Пусть — четное число. Тогда преобразуем выражение следующим образом (пусть ):

По индуктивному предположению Тогда его квадрат — тоже многочлен такого вида.

(b) Для решения этого пункта достаточно усилить индуктивное предположение и допустить, что если изначально все коэффициенты были целыми, то в итоге многочлен будет иметь целые коэффициенты.