# Given the following recurrence relation, prove using mathematical induction

How can we prove this using mathematical induction?

$m_1 = 0$

$m_k = m_{\lfloor (k/2) \rfloor} + m_{\lceil (k/2) \rceil} + k-1$ for all integers $k \geq 1$

Prove using mathematical induction that the solution to the above equation is:

$m_n = n(\lceil (log_2 n) \rceil) - 2^{\lceil (log_2 n) \rceil} + 1$ for $n \geq 0$

-
Please do not deface your questions. –  robjohn May 6 '13 at 20:11

For $n = 0$ the proposed formula gives 0, as it should. Base covered.
For the induction step, you use strong induction: Assume the formula is right for all $0 \le k < n$, and check for $n$: $$m_n = m_{\lfloor n / 2 \rfloor} + m_{\lceil n/2 \rceil} + n - 1$$ So you will need $\left\lceil \log_2 \lfloor n/2 \rfloor \right\rceil$ and the same with ceilings in the log. For this, look at $\log_2 n$ and see how it relates to the values you are looking for.