proving a closed form of recursive function using complete induction

Question

for the following recursive function: $$ T(n) = \left\{\begin{aligned} &1 &&: n=1\\ &2T(n/2)+n/2 &&: n>1 \end{aligned} \right.$$ Note:n is the power of 2 I found the closed form $$n+\frac{n log(n)}{2}$$ I need help with doing the inductive step using the complete induction

Answer 1

i finally found the answer myself. I thought sharing may help others with similar questions.For this question, ***

assume that all of the logs are base 2.

---

---

Predicate:

---

P(n):T(n)=$n+\frac{nlog(n)}{2}$ in other words the closed from of this piece wise function is $n+\frac{nlog(n)}{2}$

---

Base Case:

---

Take the smallest value of n which is 1, T(1)=1=$1+\frac{1log(1)}{2}$ since log(1)=0

---

Induction Step:

---

Induction Hypothesis: Assume for all $1 \le k < k+1$ that $k+\frac{k log(k)}{2}$ is true.

Now we have to prove that p(k+1) will be true.
T(n)=$2T(\frac{k+1}{2})+\frac{k+1}{2}$ since we know that the inputs of function T can be 2,4,8,16,....,$2^n$ this means that $1\le\frac{k+1}{2}\le k$. Therefore according to the induction hypothesis, $T(\frac{k+1}{2})=\frac{k+1}{2}+\frac{\frac{k+1}{2}log(\frac{k+1}{2})}{2}$.
$$T(n)=2T(\frac{k+1}{2})+\frac{k+1}{2}$$$$=2(\frac{k+1}{2}+\frac{\frac{k+1}{2}log(\frac{k+1}{2})}{2})+\frac{k+1}{2}$$ $$=(k+1)+\frac{k+1}{2}log(\frac{k+1}{2})+\frac{k+1}{2}$$ $$=(k+1)+\frac{k+1}{2}log(\frac{k+1}{2})+\frac{k+1}{2}(1)$$ $$=(k+1)+\frac{k+1}{2}log(\frac{k+1}{2})+\frac{k+1}{2}(log(2))$$ $$=(k+1)+\frac{k+1}{2}log(\frac{k+1}{2}2)$$ $$=(k+1)+\frac{k+1}{2}log(k+1)$$ $$=(k+1)+\frac{(k+1)log(k+1)}{2}$$
Therefore, our closed form is correct.