# Successive approximation in negative dynamic programming

I am studying Stochastic Dynamic Programming using Sheldon Ross's book, "Introduction to Stochastic Dynamic Programming." In the book, Ross defines a dynamic programming algorithm to minimize cost for unbounded costs per stage problems, and it's represented as follows:

Let $$V_0(i) = 0$$, and for $$n > 0$$, $$V_n(i) = min_a(C(i,a) + Σ_j P_{i,j}(a)V_{n-1}(j)),$$ where $$C(i,a) \geq 0$$ for every $$i$$.

The book claims that $$V_n(i) \leq V_{n+1}(i)$$, where $$V_{n}(i)$$ represents the minimal expected cost for an n-stage problem starting in $$i$$. The key observation here is that all costs are nonnegative, implying that $$V_n(i)$$ must be less than $$V_{n+1}(i)$$.

I've been trying to prove this inequality using mathematical induction, but I've hit a roadblock in my efforts.

Base Case ($$n = 0$$): For $$n = 0$$, we have: $$V_0(i) = 0$$ (given). Now, we need to prove that $$V_0(i) \leq V_1(i)$$. $$V_1(i) = min_a(C(i,a) + ∑_j P_{i,j}(a) V_0(j))$$ Since $$V_0(j) = 0$$ for all $$j$$, we can simplify this to: $$V_1(i) = min_a(C(i,a))$$.

This is a minimum value over a set of non-negative values. Since $$C(i,a)$$ is non-negative for all $$i$$ and $$a$$, the minimum value can only be zero or a positive value. Therefore, $$V_1(i)$$ is either 0 or a positive value. So, in the base case, $$V_0(i) \leq V_1(i)$$.

Inductive Hypothesis: Assume that for some arbitrary $$n$$, $$V_n(i) \leq V_{n+1}(i)$$.

Inductive Step: We want to show that $$V_{n+1}(i) \leq V_{n+2}(i)$$. We can use the formula for $$V_{n+1}(i)$$: $$V_{n+1}(i) = min_a(C(i,a) + ∑_j P_{i,j}(a)V_n(j))$$

I'm looking for assistance in completing the proof by induction.

Assume that the statement is true for all values of $$n \le K$$, and that $$C_i(a)$$, $$P_{i,j}(a)$$ are positive functions of $$a$$. Then
$$\begin{eqnarray*} V_{K+1}(i) & = & \min_a \left\{C_i(a) + \sum_j P_{i,j}(a) V_{K}(j)\right\} \\ & \ge & \min_a \left\{C_i(a) + \sum_j P_{i,j}(a) V_{K-1} (j) \right\} \\ & = & V_K (i) \end{eqnarray*}$$