1. Hello!!!

Use induction to show that if $n$ is a power of $2$ then the solution of the recurrence relation

$$\left\{\begin{matrix} 2 &, \text{ if } n=2 \\ 2T\left( \frac{n}{2} \right )+n & , \text{ if } n=2^k, \text{ for } k>1 \end{matrix}\right.$$

is $T(n)=n \lg n$.

That's what I have tried:

We will use induction on $k$ to show that $T(2^k)=2^k \cdot k$.

For $k=1 \Rightarrow n=2^1=2$ we have: $T(2)=2=2 \lg 2 \checkmark$.

We suppose that for some $k \geq 1$ it holds that $T(2^k)=2^k \cdot k$.

For $k+1$: $T(2^{k+1})=2T\left( \frac{2^{k+1}}{2} \right )+2^{k+1}=2T(2^k)+2^{k+1} \overset{\text{induction hypothesis}}{=}2 \cdot 2^k \cdot k+2^{k+1}=2^{k+1} \cdot k+2^{k+1}=2^{k+1}(k+1)$.

Thus, $\forall k \in \mathbb{N}$ it holds that $T(2^k)=2^k \cdot k$.

Could you tell me if my formulation is right or if I could improve something?

2.

3. Originally Posted by evinda
Hello!!!

Use induction to show that if $n$ is a power of $2$ then the solution of the recurrence relation

$$\left\{\begin{matrix} 2 &, \text{ if } n=2 \\ 2T\left( \frac{n}{2} \right )+n & , \text{ if } n=2^k, \text{ for } k>1 \end{matrix}\right.$$

is $T(n)=n \lg n$.

That's what I have tried:

We will use induction on $k$ to show that $T(2^k)=2^k \cdot k$.

For $k=1 \Rightarrow n=2^1=2$ we have: $T(2)=2=2 \lg 2 \checkmark$.

We suppose that for some $k \geq 1$ it holds that $T(2^k)=2^k \cdot k$.

For $k+1$: $T(2^{k+1})=2T\left( \frac{2^{k+1}}{2} \right )+2^{k+1}=2T(2^k)+2^{k+1} \overset{\text{induction hypothesis}}{=}2 \cdot 2^k \cdot k+2^{k+1}=2^{k+1} \cdot k+2^{k+1}=2^{k+1}(k+1)$.

Thus, $\forall k \in \mathbb{N}$ it holds that $T(2^k)=2^k \cdot k$.

Could you tell me if my formulation is right or if I could improve something?
Looks fine for me

Originally Posted by ZaidAlyafey
Looks fine for me
Would it be better to say at the beginning something like that?

We want to show that when $n$ is some power of $2$ then the solution of the recurrence relation is $T(n)=n \lg n$, i.e. that for $n=2^k$ where $k$ is some positive integer the solution is equal to $2^k \cdot k$.

5. Originally Posted by evinda
Would it be better to say at the beginning something like that?

We want to show that when $n$ is some power of $2$ then the solution of the recurrence relation is $T(n)=n \lg n$, i.e. that for $n=2^k$ where $k$ is some positive integer the solution is equal to $2^k \cdot k$.
Yeah, it is better.