MHB Proving $T(2^k)=2^k \cdot k$ with Induction

[evinda]

Hello! (Wave)

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? (Thinking)

 

[alyafey22]

Hello! (Wave)

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? (Thinking)

Looks fine for me :)

 

[evinda]

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$.

 

[alyafey22]

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.