How do I prove by using induction on k, that MergeSort uses $n(\log_2(n)+1)=2^k(k+1)$ comparisons?

Question

I have been asked this question in an assignment for my exam.

The assignment question is: "Assume that Merge uses (exactly) $a+b-1$ comparisons to combine two lists with a and b elements. Furthermore, assume that the length of the input list L is $n=2^k$. Prove by using induction on k, that MergeSort uses $n(log_2(n)+1)=2^k(k+1)$ comparisons to sort L. What type of induction did you use?"

I end up with the result $2^{k+1}(k+2)-1$ when I'm doing the inductive step but I think it have to be $2^{k+1}(k+2)$ I have to end up with to prove the induction step.

These are my calculations:

Basis step: I know how to do this

Inductive hypothesis: $2^k(k+1)$ comparisons for MergeSort is correct.

$P(k+1)=2^{k+1}(k+2)$ - this is what I have to end up with, right?

Sort the first list: $2^k(k+1)$ using IH

Sort the second list: $2^k(k+1)$ using IH

Merge the lists: $2^k+2^k-1$ using assumption from question

Sum them up: $2^k(k+1)+2^k(k+1)+(2^k+2^k-1)$

Reducing:

$2\cdot (2^k(k+1))+2 \cdot 2^k-1$

$2^{k+1}(k+1)+2^{k+1}-1$

$2^{k+1}(k+2)-1$

I end up with $2^{k+1}(k+2)-1$ but I think it have to be $2^{k+1}(k+2)$.

What am I doing wrong?

Answer 1

You are doing nothing wrong (except maybe when you checked the basis step). The correct formula for the number of comparisons for a list of length $2^k$ should be $(k-1)2^k + 1$.

You can see that the formula provided is not correct, as it says we would have $2$ comparisons for a list on length $1$, or $4$ comparisons for a list of length $2$, and in both cases that does not make any sense.