ГЛАВНАЯ » РЕШЕБНИК

2014-06-08   
Доказать, что для любого многочлена $P(x) \not \equiv x$ и любого числа $n \in \mathbf{N}$ многочлен
$Q_{n}(x) = P(\underbrace{P(\cdots P}_{n}(x) \cdots)) – x$
делится на многочлен $Q_{1}(x) = P(x) – x$.


Решение:


Доказательство проведем индукцией по $n \in \mathbf{N}$. Так как многочлен $Q_{1}(x)$ делится на себя, то при $n = 1$ утверждение справедливо. Пусть теперь для некоторого значения $n \in \mathbf{N}$ уже доказано тождество $Q_{n} \equiv R_{n}(x)Q_{1}(x)$, где $R_{n}(x)$ - многочлен. Тогда имеем
$Q_{n+1}(x) \equiv P(Q_{n}(x) + x) – x \equiv P(R_{n}(x)Q_{1}(x) + x) \equiv (P(R_{n}(x) Q_{1}(x) + x) - P(x)) + (P(x) – x)$.
Пусть $P(x) = \sum_{k=0}^{m}a_{k}x^{k}$, тогда
$Q_{n+1}(x) \equiv \sum_{k=0}^{m} a_{k} ((R_{n}(x)Q_{1}(x) + x)^{k} – x^{k}) + Q_{1}(x) \equiv$
$\equiv \sum_{k=0}^{m} a_{k}R_{n}(x) Q_{1}(x)S_{k}(x) + Q_{1}(x) \equiv Q_{1}(x) \cdot \left ( 1 + \sum_{k=0}^{m} a_{k}R_{n}(x)S_{k}(x) \right )$.
где обозначено
$S_{k}(x) = \sum_{j=0}^{k-1} (R_{n}(x)Q_{1}(x) + x)^{j} x^{k-j-1}$
(мы воспользовались равенством
$a^{k} – b^{k} = (a – b) \sum_{j=0}^{k-1} a^{j}b^{k-j-1}$
При $a = R_{n}(x)Q_{1}(x) + x, b = x$). Таким образом, утверждение доказано и для значения $n + 1$.