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

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!!!!

    I want to prove by induction, that the solution of the recurrence relation $T(n)=2T \left ( \frac{n}{2} \right )+n^2, n>1 \text{ and } T(1)=1$ is $n(2n-1)$.

    We have to suppose that $n=2^k, k \geq 0$, right?

    Do I have to prove the solution by induction with respect to $n$ or to $k$ ?

  2. # ADS
    Circuit advertisement
    Join Date
    Always
    Posts
    Many
     

  3. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    MHB Coder
    Klaas van Aarsen's Avatar
    Status
    Offline
    Join Date
    Mar 2012
    Location
    Leiden
    Posts
    8,413
    Thanks
    5,447 times
    Thanked
    14,630 times
    Thank/Post
    1.739
    Awards
    MHB Pre-University Math Award (2018)  

MHB Model Helper Award (2017)  

MHB Best Ideas (2017)  

MHB Analysis Award (2017)  

MHB Calculus Award (2017)
    #2
    Quote Originally Posted by evinda View Post
    Hello!!!!

    I want to prove by induction, that the solution of the recurrence relation $T(n)=2T \left ( \frac{n}{2} \right )+n^2, n>1 \text{ and } T(1)=1$ is $n(2n-1)$.

    We have to suppose that $n=2^k, k \geq 0$, right?

    Do I have to prove the solution by induction with respect to $n$ or to $k$ ?
    Hi!!

    I'd pick $k$, since $T(n)$ is not defined for all $n \in \Bbb N$.

    Btw, do you really have to use induction?

  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 I like Serena View Post
    I'd pick $k$, since $T(n)$ is not defined for all $n \in \Bbb N$.

    Btw, do you really have to use induction?
    The exercise asks the following:

    Solve the recurrence relation $ \displaystyle{T(n)=\left\{\begin{matrix}
    1 &,n=1 \\
    2T \left(\frac{n}{2} \right )+n^2 &, n>1
    \end{matrix}\right.}$

    and then, prove that the solution you found is right, using mathematical induction.

    So, do we have to do it like that?

    We suppose that $n=2^k, k \geq 0$.

    • $k=0 \Rightarrow n=1: T(1)=1=1\cdot (2 \cdot 1-1) \checkmark$
      $$$$
    • We suppose that the relation stands for any $k>1$, so $T(2^k)=2^k(2^{k+1}-1)$
      $$$$
    • We will show that the relation stands for $k+1$.

      $$T(2^{k+1})=2T \left (\frac{2^{k+1}}{2} \right )+(2^{k+1})^2=2T(2^k)+2^{2k+2}=2 (2^k(2^{k+1}-1))+2^{2k+2}\\ =2^{2k+2}-2^{k+1}+2^{2k+2}=2^{k+1}(2 \cdot 2^{k+1}-1)$$

  5. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    MHB Coder
    Klaas van Aarsen's Avatar
    Status
    Offline
    Join Date
    Mar 2012
    Location
    Leiden
    Posts
    8,413
    Thanks
    5,447 times
    Thanked
    14,630 times
    Thank/Post
    1.739
    Awards
    MHB Pre-University Math Award (2018)  

MHB Model Helper Award (2017)  

MHB Best Ideas (2017)  

MHB Analysis Award (2017)  

MHB Calculus Award (2017)
    #4
    Quote Originally Posted by evinda View Post
    The exercise asks the following:

    Solve the recurrence relation $ \displaystyle{T(n)=\left\{\begin{matrix}
    1 &,n=1 \\
    2T \left(\frac{n}{2} \right )+n^2 &, n>1
    \end{matrix}\right.}$

    and then, prove that the solution you found is right, using mathematical induction.

    So, do we have to do it like that?

    We suppose that $n=2^k, k \geq 0$.

    • $k=0 \Rightarrow n=1: T(1)=1=1\cdot (2 \cdot 1-1) \checkmark$
      $$$$
    • We suppose that the relation stands for any $k>1$, so $T(2^k)=2^k(2^{k+1}-1)$
      $$$$
    • We will show that the relation stands for $k+1$.

      $$T(2^{k+1})=2T \left (\frac{2^{k+1}}{2} \right )+(2^{k+1})^2=2T(2^k)+2^{2k+2}=2 (2^k(2^{k+1}-1))+2^{2k+2}\\ =2^{2k+2}-2^{k+1}+2^{2k+2}=2^{k+1}(2 \cdot 2^{k+1}-1)$$
    Perfect!


    Alternatively, note that $T(n)=n(2n-1)$ fits in the original equation, including the boundary condition that $T(1)=1$.
    Therefore it is a solution.

    $ \displaystyle T(1)=1(2\cdot 1 - 1)=1$

    $ \displaystyle n(2n-1)=T(n)=2T\left(\frac n2\right)+n^2 = 2\cdot \frac n 2 \left(2\cdot \frac n 2 - 1\right) + n^2 = n(n-1) + n^2 = n(2n-1)$

    In other words, there is no real need for a proof by induction.
    Just verifying that the proposed solution satisfies the problem statement is enough.

  6. 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)
    #5 Thread Author
    Or do I have to suppose maybe, at the second step, that the relation stands for any $k \geq 0$ ?

  7. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    MHB Coder
    Klaas van Aarsen's Avatar
    Status
    Offline
    Join Date
    Mar 2012
    Location
    Leiden
    Posts
    8,413
    Thanks
    5,447 times
    Thanked
    14,630 times
    Thank/Post
    1.739
    Awards
    MHB Pre-University Math Award (2018)  

MHB Model Helper Award (2017)  

MHB Best Ideas (2017)  

MHB Analysis Award (2017)  

MHB Calculus Award (2017)
    #6
    Quote Originally Posted by evinda View Post
    Or do I have to suppose maybe, at the second step, that the relation stands for any $k \geq 0$ ?
    Oh yes.

Similar Threads

  1. Mathematical induction
    By ineedhelpnow in forum Calculus
    Replies: 13
    Last Post: July 23rd, 2014, 19:01
  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

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