Алгоритм Нкоби — Перрона ЗЙ9'

если t=2, ..., m, и rfi,i.o=degpi,o=deg l=Si—Si, если t=l.

Предположим , что доказываемая формула верна при к, меньших /^0 (/=0), тогда при/j=Äo имеем

/ m

di , ko . o =degi4f,/^^=deg ^1 /^m-/,^A.VM ^ max {degpm^f,k.)+ max (degi4/.;fe.~/-i),

/ s=0 , . . . ^W /s=sO,...,W

что по нашему предположению не превосходит

Sk^ — Xf + max 5feo~/-i = — %i+ Sk..

/ eo , . . . , m

Итак , при /=0 формула (20) установлена.

Допустим далее, что утверждение леммы доказано при всех цательных /, меньших /о, для всех k>lo. Наши дальнейшие рассуждения будут зависеть от того, какое h.

Рассмотрим сначала случай, когда /о^т—1.

Разложив сумму в тождестве (18) на две и воспользовавшись тем> Что при /<т+1

получим

/ » m

/ а

( здесь мы считаем, что Pf-.,„-i, ^^+1=0 при î—/о—1<0). Ввиду того, чта /о—/<0, для оценки степеней Di^i^^i^^j можно воспользоваться формулой (20). При i^lo + l имеем

du^uU ^ nîax ( max (deg pm^Jr^i + du,. V/)^ deg p^/e-i.^+i + deg Л/„о) ^ ^max(^jTiax^ ((s/,^,- 1)_X, + S/, + ['"" |^+ ^^]), (s^..i-1)+S/.)< ^тах(-Я,+ 5/,,1-1 + Г1=А1, S/.+i-lW

так km[i^:iMJl|==o, Xi== 1 npir 1 :^/^<t^m.