Facebook Page
Twitter
RSS
+ Reply to Thread
Results 1 to 4 of 4

Thread: Induction

  1. MHB Master
    MHB Site Helper
    MHB Math Helper
    evinda's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,642
    Thanks
    3,525 times
    Thanked
    1,097 time
    Awards
    MHB Model User Award (2016)  

MHB Model User Award (2014)
    #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. # ADS
    Circuit advertisement
    Join Date
    Always
    Posts
    Many
     

  3. زيد اليافعي
    MHB Site Helper
    MHB Math Helper
    ZaidAlyafey's Avatar
    Status
    Offline
    Join Date
    Jan 2013
    Location
    KSA
    Posts
    1,666
    Thanks
    3,673 times
    Thanked
    3,866 times
    Thank/Post
    2.321
    Awards
    MHB Math Notes Award (2014)  

MHB Best Ideas (2014)  

MHB Best Ideas (Jul-Dec 2013)  

MHB Analysis Award (Jul-Dec 2013)  

MHB Calculus Award (Jul-Dec 2013)
    #2
    Quote Originally Posted by evinda View Post
    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

  4. MHB Master
    MHB Site Helper
    MHB Math Helper
    evinda's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,642
    Thanks
    3,525 times
    Thanked
    1,097 time
    Awards
    MHB Model User Award (2016)  

MHB Model User Award (2014)
    #3 Thread Author
    Quote Originally Posted by ZaidAlyafey View Post
    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$.
    Last edited by evinda; February 25th, 2015 at 18:13.

  5. زيد اليافعي
    MHB Site Helper
    MHB Math Helper
    ZaidAlyafey's Avatar
    Status
    Offline
    Join Date
    Jan 2013
    Location
    KSA
    Posts
    1,666
    Thanks
    3,673 times
    Thanked
    3,866 times
    Thank/Post
    2.321
    Awards
    MHB Math Notes Award (2014)  

MHB Best Ideas (2014)  

MHB Best Ideas (Jul-Dec 2013)  

MHB Analysis Award (Jul-Dec 2013)  

MHB Calculus Award (Jul-Dec 2013)
    #4
    Quote Originally Posted by evinda View Post
    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.

Similar Threads

  1. Induction
    By evinda in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 5
    Last Post: October 9th, 2014, 15:30
  2. Induction
    By delc1 in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 5
    Last Post: June 20th, 2014, 05:25
  3. Induction
    By kp100591 in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 1
    Last Post: May 19th, 2014, 12:32
  4. Induction C(n,k)
    By evinda in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 2
    Last Post: April 24th, 2014, 19:58
  5. Induction Help
    By crypt50 in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 2
    Last Post: June 30th, 2013, 11:16

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards