The maximal solution of a restricted subadditive inequality in numerical analysis (Q1093821)

For a fixed non-negative integer p, let \(U_{2p}=\{U_{2p}(n)\}\), \(n\geq 0\), denote the sequence that is defined by the initial conditions \(U_{2p}(0)=U_{2p}(1)=U_{2p}(2)=...=U_{2p}(2p)=1\) and the restricted subadditive recursion \[ U_{2p}(n+2p+1)=\min_{0\leq \ell \leq p}(U_{2p}(n+\ell)+U_{2p}(n+2p-\ell)),\quad n\geq 0. \] \(U_{2p}\) is of importance in the theory of sequential search for simple real zeros of real valued continuous 2p-th derivatives. The main result of the present paper is that \(U_{2p}\) satisfies the system of \(p+1\) difference equations \[ U_{2p}((p+1)j+i+2p+1)=\begin{cases} U_{2p}((p+1)j+p-1)+U_{2p}((p+1)(j+1)+2i), &\text{if \(0\leq i<[(p+1)/2]\)} \\ U_{2p}((p+1)j+2i)+U_{2p}((p+1)(j+1)+p-1), &\text{if \([(p+1)/2]\leq i\leq p\)}.\end{cases} \] As a consequence of the above result several closed form expressions for \(U_{2p}(n)\), \(n>2p\) are determined and the existence of exactly \(p+1\) limit points \((1+1/(p+1+i)\), \(0\leq i\leq p)\) of the associated sequence \(\{U_{2p}(n+1)/U_{2p}(n)\}\), \(n\geq 0\) are proved.