Induction and Recursion I have NO idea!

  1. Mar 8, 2012 #1
    I think I'm pretty good at standard induction. Never had a problem.

    Induction and recursion is mercilessly whooping my ***.

    1. The problem statement, all variables and given/known data

    Let a1 = 1. For each natural number n > 1, let an = 3an-1 - 1.

    Prove that for each natural number n, an = 1/2(3n-1 + 1)

    2. Relevant equations



    3. The attempt at a solution

    WAT

    I can "build it." And I don't even feel comfortable doing that. Let S be the set of n for which the theorem holds.

    Let n = 2

    Theorem holds.

    Let n = 3

    Theorem holds.

    So 2,3 are elements of S.

    (Do I have to show it for 2? Or more? Or just one? Why?)

    Suppose that n >= 3 and {1,2,....,n} is a subset of S.

    I have no idea what to do. At all. Can someone please explain recursion induction to me?
     
  2. jcsd
  3. Mar 8, 2012 #2
    I think I see..

    I know that
    an+1 = 3an - 1 because that's the definition.

    And based on my assumption, an = 1/2(3n-1[/SUP + 1)

    So I can plug it in, and algebraically show that an+1 equals 1/2(3n[/SUP + 1)

    Am I on the right track?
     
  4. Mar 8, 2012 #3

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor

    Yes, that's the idea. Can you do that?
     
  5. Mar 8, 2012 #4
    Yes, that's what I tried and it worked out.

    So for this example, I'd really only need to show it to be true for one value, right?
     
  6. Mar 8, 2012 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor

    Yes, you only need to show it's true for n=1 and you need to show the induction step.
     
  7. Mar 8, 2012 #6
    Do you mean n = 2? If n = 1, an-1 is undefined?
     
  8. Mar 8, 2012 #7

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor

    Yes, check it for n=2 of course.
     
  9. Mar 8, 2012 #8
    Ok, got it. Thanks again!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?