577
правок
Изменения
→Асимптотика
Остается показать, что если равенство (2) выполняется для <tex>T = d_i - m</tex>, тогда оно выполняется и для <tex>T = 1, \ldots d_i - m - 1</tex>. Докажем индукцией по <tex>T</tex>, что равенство (2) выполняется для <tex>T = 1, \ldots d_i - m</tex>, взяв как базу <tex>T = d_i - m</tex>.
#''База.'' По теореме из [[Opij1di#доказательство корректности|доказательства корректности]] <tex>h^V(1) \leqslant m</tex> означает, что <tex>V</tex> может быть выполнено вовремя. С другой стороны, если <tex>h^V(1) \leqslant m</tex>, то выполняется (2), так как <tex>h^V(t) \leqslant m</tex> для всех <tex>t \geqslant 2</tex> по построению <tex>h^V</tex>.
#''Переход.''Предположим, что (2) выполняется для некоторого <tex>T \in (1, d_i - m]</tex>. Рассмотрим два случая в зависимости от значения <tex>h^V(T)</tex>:#:<tex>(a)</tex> Пусть <tex>h^V(T) = m</tex>. Так как равенство (2) выполняется для <tex>T</tex>, то верно <tex>(T - 1)m \geqslant \sum\limits_{t = 1}^{T}h^V(t) - m = \sum\limits_{t = 1}^{T - 1}h^V(t)</tex>. Следовательно, (2) выполняется и для <tex>T - 1</tex>.#:<tex>(b)</tex> Пусть <tex>h^V(T) < m</tex>.
}}
