1

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?

Ariel Serranoni
  • 494
  • The reasoning is correct, but what you need as a final step is substitution $k=k^\ast$ in the last inequality you've got (and not the original formula). – metamorphy Sep 05 '18 at 03:27
  • Well, doing as you suggested I obtained $M(n+1)\geq\frac{1}{2}(\frac{n-1}{2}+1)\log_2(\frac{n-1}{2}+1)+\frac{1}{2}(\frac{n+1}{2}+1)\log_2(\frac{n+1}{2}+1)+n+1$. Any idea on how does this help out? – Ariel Serranoni Sep 05 '18 at 03:42
  • The second of these three terms is $\geqslant$ the first. If you replace the value of the second term with the value of the first one, you arrive exactly at what you need. – metamorphy Sep 05 '18 at 03:47
  • Hmm.. I think I'm missing something here, following your steps, I derived $M(n+1)\geq \frac{1}{2}((n+1)\log_2(n+1)-n+1)n+1$. I can use the same argument you suggested in your last comment to get rid of the extra $\frac{n+1}{2}$, right? Moreover, shouldn't I obtain $M(n+1)\geq\frac{1}{2}(n+2)\log_2(n+2)$ to conclude my induction step? – Ariel Serranoni Sep 05 '18 at 04:16
  • Oops, I'm hurried with my second comment. Gonna post it fixed as an answer. – metamorphy Sep 05 '18 at 04:23

1 Answers1

1

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.

metamorphy
  • 39,111