Some Recurrence Relations of Recursive Minimization
C. J. K. Batty, M. J. Pelling, Douglas G. Rogers · SIAM Journal on Algebraic and Discrete Methods · 1982
The recursive minimization problem\[ f ( n ) = \min \left\{ \sum^r_{i = 1} f ( a_i ) \right\} + g ( n ), \] where the minimum is taken over all r-tuples $a = ( a_1 , \cdots ,a_r )$ of integers $a_i $, such that $0\leqq a_i < n$, $1\leqq i\leqq r$, $\sum^r_{i = 1} a_i = n$, is studied. Necessary and sufficient conditions on $g( n )$, satisfied by many nonnegative convex sequences, are found for the solution to be given by the recurrence relation \[f ( n ) = \sum_{i = 1}^r f \left( \left[ \frac{n + i - 1}{r} \right] \right) + g ( n ).\] A similar recurrence relation is found for the solution when g satisfies certain concavity conditions.