Question 3 Redone

$$\begin{array}{rl}T(0)& =1\\ T(1)& =1\\ T(n)& =2\cdot T\left(\begin{array}{c}\lceil \frac{n}{2}\rceil \end{array}\right)+3n\end{array}$$

Show that $T(n)\ge 2n{\log }_{2}n+(2n-1)$ for all $n\ge 1$:

1. Base Case: Show that $T(n)\ge 2n{\log }_{2}n+(2n-1)$ for $n=1$:

$$\begin{array}{rl}T(n)& \ge ?2n{\log }_{2}n+(2n-1)\\ 1& \ge ?2\cdot 0+2-1\\ 1& \ge 1\text{ as required}\end{array}$$

2. Inductive Case: Assume that $T(m)\ge 2m{\log }_{2}m+(2m-1)$ for all $1\le m\le k$ for some $k\ge 1$.

$$\begin{array}{rl}\text{RHS / Goal}& =2(k+1){\log }_2(k+1)+(2(k+1)-1)\\ & =2(k+1){\log }_2(k+1)+(2k+1)\end{array}$$

We have that for $n=k+1$:

$$\begin{array}{rl}T(k+1)& =2\cdot T\left(\begin{array}{c}\lceil \frac{k+1}{2}\rceil \end{array}\right)+3(k+1)\\ & \ge 2\cdot \left[\begin{array}{c}2\left(\begin{array}{c}\lceil \frac{k+1}{2}\rceil \end{array}\right){\log }_2\left(\begin{array}{c}\lceil \frac{k+1}{2}\rceil \end{array}\right)+(2\left(\begin{array}{c}\lceil \frac{k+1}{2}\rceil \end{array}\right)-1)\end{array}\right]+3(k+1)\text{(by I.H.)}\\ & \ge 2\cdot \left[\begin{array}{c}2\left(\begin{array}{c}\frac{k+1}{2}\end{array}\right){\log }_2\left(\begin{array}{c}\frac{k+1}{2}\end{array}\right)+(2\left(\begin{array}{c}\frac{k+1}{2}\end{array}\right)-1)\end{array}\right]+3(k+1)\\ & =2\cdot \left[\begin{array}{c}(k+1){\log }_2\left(\begin{array}{c}\frac{k+1}{2}\end{array}\right)+(k+1-1)\end{array}\right]+3(k+1)\\ & =2(k+1){\log }_2\left(\begin{array}{c}\frac{k+1}{2}\end{array}\right)+2k+3(k+1)\\ & =2(k+1){\log }_2\left(\begin{array}{c}\frac{k+1}{2}\end{array}\right)+5k+3\\ & =2(k+1){\log }_2(k+1)-2(k+1){\log }_2(2)+5k+3\\ & =2(k+1){\log }_2(k+1)-2k-2+5k+3\\ & =2(k+1){\log }_2(k+1)+(3k+1)\\ & \ge 2(k+1){\log }_2(k+1)+(2k+1)\\ & \ge \text{RHS as required}\end{array}$$

Hence, by strong induction, $T(n)\ge 2n{\log }_{2}n+(2n-1)$ for all $n\ge 1$.