Results 1 to 3 of 3

Math Help - Need help understanding a proof by induction

  1. #1
    Newbie
    Joined
    Oct 2011
    Posts
    22

    Need help understanding a proof by induction

    I am working through some of the problems in the appendix of my algorithms book...

    They are showing that \sum_{k=0}^{n}3^k is  O(3^n) or \sum_{k=0}^{\n}3^k <= c3^n for some constant c

    The initial condition was shown to be true as long as c >= 1. They assume that the bound holds for n and then show that it holds for n+1

    \sum_{k=0}^{n+1}3^k = \sum_{k=0}^{n}3^k +3^{n+1} <= c3^n + 3^{n+1} = (\frac{1}{3} + \frac{1}{c})c3^{n+1} <= c3^{n+1}
    as long as (\frac{1}{3} + \frac{1}{c}) <= 1 or c>=3/2

    What I don't get is (\frac{1}{3} + \frac{1}{c})c3^{n+1} I see that I can distribute the c3^{n+1} to get the previous result. But Why do we want this form?
    Is it because I want to express c3^n + 3^{n+1}in a way that I can make it comparable to c3^{n+1}?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,619
    Thanks
    592

    Re: Need help understanding a proof by induction

    Hey restin84.

    The basic reason is to prove that there exists some finite constant real number c that satisfies the identity: what that constant is is not of too much concern. The concern is that the constant actually exists and is a finite real number.

    Remember that you are looking for a final constant c that exists not any of the intermediate c's used in the induction step.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Need help understanding a proof by induction

    During the induction, you've gotten to here:

    \sum_{k=0}^{n+1}3^k  \le c3^n + 3^{n+1} ,

    but, in order to complete the induction, you're SEEKING to be able to write this:

    "And so, assuming it's true for all values up to n, have shown that it follows that \sum_{k=0}^{n+1}3^k \le c3^{n+1}.

    Therefore, it being true up to n implies it's true up to n+1, and since it was shown true for n=1, this proves, by induction, that it's true for all n."

    ----

    So you have this: \sum_{k=0}^{n+1}3^k \le c3^n + 3^{n+1} ,

    and you want to show that that implies this: \sum_{k=0}^{n+1}3^k \le c3^{n+1}.

    Well, you do the algebraic manipulation that you wrote there to show that the first situation implies the second situation (when c >=3/2).
    Last edited by johnsomeone; September 25th 2012 at 08:53 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help understanding proof
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: November 9th 2010, 10:58 AM
  2. Help Understanding a Proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: December 23rd 2009, 08:37 PM
  3. Help understanding this theorem/proof
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: December 8th 2009, 03:39 PM
  4. Understanding logic of proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 10th 2009, 09:33 AM
  5. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM

Search Tags


/mathhelpforum @mathhelpforum