Results 1 to 2 of 2
Like Tree1Thanks
  • 1 Post By MarkFL

Math Help - Proof by Induction - Recurrence Relation

  1. #1
    Junior Member
    Joined
    Nov 2012
    From
    Manchester
    Posts
    30

    Proof by Induction - Recurrence Relation

    PROBLEM

    Define a recurrence relation H(n) by the rules
    H(0) = 1, H(1)=1, H(2) = 3, and
    H(n) = H(n-1) + H(n-3) -H(n-2) + 2 for n >= 3.

    Prove by induction that H(n) = n+1 for all n = 0,1,2,...

    My WORK
    - Base case:
    P(0) asserts that 0+1 = 1. This is true, and thus the base case is completed.

    - Inductive step:
    Assume P(k): 1+2+...+k = k+1
    P(k) is therefore our inductive hypothesis.

    Now, we must prove that if P(k) holds, then P(k+1) must also hold. Hence, we add (k+1) on both sides of the equality.

    /* This is where I get lost. Any help is much appreciated */

    1+2+...+k+(k+1) = [1+2+...+k]+1 + (k+1)
    = (k+1) + (k+1)
    = k+k+1+1
    = 2k + 2
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor MarkFL's Avatar
    Joined
    Dec 2011
    From
    St. Augustine, FL.
    Posts
    1,988
    Thanks
    734

    Re: Proof by Induction - Recurrence Relation

    Here's what you should be doing (or something similar)

    The base case P_0 is given, since H(0)=0+1=1.

    I think you mean to give H(1)=2 in your definition.

    Now, state the induction hypothesis P_k

    H(k)=k+1

    From the recursive definition, we may state:

    H(k+1)-H(k)=H(k-2)-K(k-1)+2

    Now, how can you rewrite the right side using the induction hypothesis? Once you do this, then add it to P_k.
    Thanks from aprilrocks92
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation proof
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 11th 2011, 05:44 AM
  2. big o recurrence relation
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 4th 2011, 04:49 AM
  3. Proof of a trig relation using induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 9th 2010, 10:07 AM
  4. Recurrence Relation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 22nd 2010, 06:14 AM
  5. Recurrence Relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 19th 2007, 07:54 PM

Search Tags


/mathhelpforum @mathhelpforum