Как доказать выпуклость?

Математика
1

Пусть есть последовательность чисел C, выполняется 1 \leq C_i для каждого i, пусть есть последовательность последовательность ans_{i, j},

  • \large ans_{1, 1} = 0.
  • Если i > 1 и j > 1 то \large ans_{i, j} = min(ans_{i - 1, j} + j ^2, ans_{i,j - 1} +c_i).
  • Если i > 1 и j = 1 то \large ans_{i, j} = ans_{i - 1, j} + j^2.
  • Если i = 1 и j > 1 то \large ans_{i, j} = ans_{i, j - 1} + c_i.

Нужно доказать что \large ans_{i, j} - ans_{i, j - 1} \leq ans_{i, j + 1} - ans_{i, j}.

2

Ну один вариант с помощью инварианты (или как Invariance Principle по-русски зовется).

Сначала показать, что неравенство держится в начале последовательности (когда наименьшее слагаемое это ans_{1,1}), а потом показать что оно не изменяется при любом из возможных переходов. И в конце апеллировать к той самой инварианте.

1 лайк
3

Пункт i>1, j=1 верно переписан? Зачем нужно j^2 ?