Изменения

При переходе от сортирующей сети с <tex>n</tex> входами к сети с <tex>n + 1</tex> входами, добавляем <tex> n </tex> дополнительных компараторов (<tex>[1:2],[2:3]\dots[n:n + 1]</tex> или <tex>[n + 1:n],[n:n + 1]\dots[1:2]</tex>, т.к. возможны две стратегии добавления). В полученной "треугольной" сети можно заметить, что <tex>n - 1</tex> компаратор входят в уже существующие слои (<tex>[2:3],[3:4]\dots[n:n + 1] </tex> или <tex>[n:n + 1],[n - 1:n - 2]\dots[2:3]</tex>).т.е. на можно объединить компараторы в слои так, что в каждом четном слое самым верхним компаратором будет <tex> [2:3] </tex>, а на нечетном <tex>[1:2]</tex>,т.к. количество этих компараторов <tex> n - 1</tex> и <tex> n - 2 </tex>, но тогда один компаратор из предыдущей сортирующий сети и один из добавленных не вносят вклад в количество слоев. Тогда видно, что количество слоев увеличилось на <tex> 2 = S(n + 1) - S(n) </tex>, т.е. наш переход выполняется и формула верна. Что и требовалось доказать.