Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
    
Please do not deface your questions. –  robjohn May 6 '13 at 20:11

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.