Proof by induction of recurrence relation

Question

I've been shown the following proof by induction of $P(n)$ where $n$ is a positive integer presumably. This is in the context of algorithmic analysis.

$ P(n):T(n) = \begin{cases} 2T([\frac{n}{2}])+n &,n>1\\ 1 &,n=1 \end{cases} \Rightarrow T(n) = n\log_2 n + n $

Base case, $P(1) :T(1) =1 =1log_2 1+1$

Assume $P(n)$ is true for all $n < m$, show $P(m)$ is true \begin{align} \text{LHS } P(m):T(m) &= 2T(\frac{m}{2})+m \\ &= 2(\frac{m}{2}\log_2\frac{m}{2} + \frac{m}{2}) + m \\ &= m\log_2 m + m \\ &= P(m) \end{align}

I have a few problems with this, firstly it isn't necessary that $n/2$ eventually reaches $1$ so is there even a solution (could this be avoided by changing the condition to $n \leq 1$)?

Secondly the strong induction step seems somewhat dodgy as we are dividing $n$ by $2$ each time so it isn't necessary that the $n/2$ case be covered (5 to 2.5 for example). We could then include all the halves going $(0.5,1,1.5)$ in our steps but then we wouldn't have $0.25$ and so on and kind of misses the point of induction anyway? I'm just a bit confused and any insight would be greatly appreciated.

Answer 1

From the way you write $T(n)=2T\left(\color{red}{[}\frac{n}{2}\color{red}{]}\right)$, I think you misinterpreted either the function floor $\lfloor\frac{n}{2}\rfloor$, corresponding to the lower integer part, or the function ceiling $\lceil\frac{n}{2}\rceil$, corresponding to the higher integer part.

You probably didn't make the difference between either of these functions and the square brackets $[\frac{n}{2}]$, which are redundant.

The use of integer part functions solves your problem of distinguishing between even and odd cases - both are rounded (up or down) to an integer.