I got a dynamic programming problem as described below:
There are two function $g(X_m)$ and $f(x_i,y_i)$, where $X_m=\sum_{i=1}^m x_i$ and $x_i$, $y_i$ are both positive integers such that $x_i\le y_i$. The problem is to find the sequence $(x_i,y_i)_{i=1}^m$ which maximizes $$\sum_{i=1}^m g(X_i)f(x_i,y_i)$$ for given $M=X_m$ and $N=\sum_{i=1}^m y_i$. It should be noted $m$ can be any number from $\{1,2,\ldots,M\}$. The function $g(X_m)$ is non-increasing along $X_m$ and $f$ is non-decreasing along $x_i$ and $y_i$.
Let $(x^*_i,y^*_i)_{i=1}^m$ be the solution and $C(M,N)=\sum_{i=1}^m g(X^*_i)f(x^*_i,y^*_i)$, where $X^*_j=\sum_{i=1}^jx^*_i$. We have already known that $$C(N,M)=\max_{\{x,y|x\leq M , y\leq N, x\leq y\}}C(M-x,N-y)+g(M)g(x,y)$$ can be solved recursively hence dynamic programming is then applied.
According to the numerical results, we observed that the solution $(x^*_i,y^*_i)_{i=1}^m$ forms an non-increasing sequence, i.e., $x^*_i\ge x^*_{i+1}$ and $y^*_i\ge y^*_{i+1}$. However, we can not prove it. Is there any reference or idea to prove this property?
Remark: Except for the non-decreasing and non-increasing properties, function $f(x,y)$ has another property of $f(x_1,y_1)+f(x_2,y_2)\le f(x_1+x_2,y_1+y_2)$, and function $g(x)=\sum_{i=0}^S {x \choose i} p^i(1-p)^{x-i}$, which is a binomial CDF, $\tt{binocdf(S,x,p)}$ in Matlab, with predefined $S$ and $p$.