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?   Reply With Quote

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   Reply With Quote 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$.  Reply With Quote

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.  Reply With Quote

+ Reply to Thread \$t2^k=2^k, cdot, induction, show, text #### Posting Permissions 