Изменения

Так как <tex> q \not\equiv 0 </tex>, хотя бы один <tex> q_i \not\equiv 0 </tex>. Пусть <tex> j = max \{ i | q_i \not\equiv 0\} </tex>.По формуле полной вероятности имеем:<tex> p(q = 0) = p(q = 0 | q_j = 0) p(q_j = 0) + p(q = 0 | q_j \ne 0) p(q_j \ne 0) </tex>. Заметим, что <tex> q_j - </tex> полином от <tex> n - 1 </tex> переменных, а потому к нему применимо предположение индукции. Кроме того, <tex> deg \enskip q_j \le d - j </tex>. Таким образом, <tex> p(q = 0 | q_j = 0) p(q_j = 0) \le 1 * \frac{d - j}{|S|} </tex>. Для получения оценки второго слагаемого зафиксируем некоторый набор <tex> \{x_1, ..., x_{n-1}\} </tex>, для которого <tex> q_j(x_1, ..., x_{n-1}) \ne 0 </tex>.Тогда для <tex> q(x_1, ... x_n) </tex> как для полинома 1 переменной степени <tex> j </tex> будет выполнено:<tex> p(q = 0 | q_j \ne 0) p(q_j \ne 0) \le \frac{i}{|S|} * 1 </tex>. <tex> p(q = 0) \le \frac{d-j}{|S|} + \frac{j}{|S|} = \frac{d}{|S|} </tex>, что и требовалось доказать.