Изменения
Нет описания правки
II. Рассмотрим два варианта, когда <tex>x = y</tex> (1) и <tex>x \ne y</tex> (2):
#Пусть <tex>x = y</tex>, тогда <tex>d = 0</tex> (по свойству №1), так как <tex>d(x,z)</tex> и <tex>d(z,y)</tex> не могут быть меньше нуля, значит их сумма также неотрицательна <tex>(0 \le d(x,z) + d(z,y))</tex>, следовательно, неравенство <tex>~d(x,y) \le d(x,z) + d(z,y)</tex> выполняется.
#Пусть слова <tex>x \ne y</tex>.а) ''База индукции:'' Пусть слова <tex>x</tex> и <tex>y</tex> отличаются в некоторой позиции. Тогда какое бы слово <tex>z</tex> мы ни не взялионо будет отличатся хотя бы от одного из слов <tex>x</tex> или <tex>y</tex>. А это означает, в каждой конкретной позиции что неравенство <tex>~d(x,y) \le d(x,z) + d(в которой было расхождение у слов z,y)</tex> выполняется. б) Пусть неравенство <tex>~d(x,y) \le d(x,z) + d(z,y)</tex> и выполняется при <tex>~d(x,y) = k</tex>. <tex>(*) </tex> Докажем, что оно будет отличаться хотя бы от одного верно для <tex>~d(x,y) = k + 1</tex>. Для <tex>k</tex> позиций из них. Перебрав все такие позиции получим то, что <tex>k + 1</tex> общее количество различий между словами отличий слова <tex>x</tex> от <tex>z</tex> и слова <tex>y</tex> от <tex>z</tex>, благодаря предположению <tex>(*)</tex>, не превосходит общее меньше, чем количество различий между словами отличий слова <tex>x</tex> от <tex>y</tex>. Рассмотрим оставшуюся позицию, в которой отличаются слова <tex>x</tex> и <tex>y</tex>. Так как какое бы слово <tex>z</tex> и словами мы не взяли оно, в этой позиции, будет отличатся хотя бы от одного из слов <tex>x</tex> или <tex>y</tex>, то неравенство <tex>~d(x,y) \le d(x,z) + d(z,y)</tex> и для <tex>~d(x,y) = k + 1</tex>верно. А это означает Индуктивное предположение верно, значит, что неравенство <tex>~d(x,y) \le d(x,z) + d(z,y)</tex> выполняетсядля любого натурального k (k - количество отличий слова <tex>x</tex> от <tex>y</tex>).}}
