I've been trying to solve the following problem: Consider the following recurrence: $$ \begin{cases} M(0)=1\\ M(1)=1\\ M(n)=\min_{0\leq k\leq n-1}\{M(k)+M(n-k-1)\}+n \text{, if } n\geq 2 \end{cases} $$ Show that $M(n)\geq \frac{1}{2}(n+1)\log_2(n+1)$.
Of course, I'm showing this by induction. The base case is trivial. For the induction step, my (incomplete) attempt is the following:
Assume that our result holds for $i=1,\cdots,n$. It follows: \begin{align*} M(n+1)&=\min_{0\leq k\leq n}\{M(k)+M(n-k)\}+n+1\\& \geq\min_{0\leq k\leq n}\{\frac{1}{2}(k+1)\log_2(k+1)+\frac{1}{2}(n-k+1)\log_2(n-k+1)\}+n+1\\& \geq\min_{k\in[0,n]}\{\frac{1}{2}(k+1)\log_2(k+1)+\frac{1}{2}(n-k+1)\log_2(n-k+1)\}+n+1. \end{align*}
Calculating the first and second-order derivatives of the function being minimized, we obtain that $k^\ast=\frac{n-1}{2}$ is the minimizer of such function. Substituting in the original formula yields(?): $$ M(n+1)\geq M(\frac{n-1}{2}) + (n+1) $$
Is this reasoning correct? Can anyone help me to finish this problem?
From the OP we have $M(n + 1) \geqslant n + 1 + \displaystyle\frac{1}{2}\min_{x \in [0, n]}f(x)$, where $$f(x) = (x + 1)\log_2(x + 1) + (n - x + 1)\log_2(n - x + 1),$$ $$f'(x) = \log_2(x + 1) - \log_2(n - x + 1),$$ and the minimum is at $x = n/2$ (compare with the statement in the question). Thus, $$M(n + 1) \geqslant n + 1 + \frac{n + 2}{2}\log_2\frac{n + 2}{2} = \frac{n + 2}{2}\log_2(n + 2) + \frac{n}{2}.$$ The last term can be dropped.