Results 1 to 3 of 3

Math Help - Induction!

  1. #1
    Newbie
    Joined
    Mar 2008
    From
    Maine
    Posts
    13

    Induction!

    I'm not sure how to go about setting up the steps for this problem.

    a1 = 1, a2 = 1 and an = 2an-1 + an-2 for all n ≥ 3. prove an is odd for all n≥1.


    first six are 1,1,3,7,17,41



    I could also use help on another problem...
    proving (3,5,7) is the only prime triple - consecutive odd integers which are all prime -

    to do this i prove that for any odd integer k, one of the integers 2k+1, 2k+3, and 2k+5 must be divisible by 3.

    I know i need to use cases for this.

    how does this then show that (3,5,7) is the only prime triple?


    thanks for the input guys.

    kyle
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    The characteristic equation is a^{2}-2a-1=0

    It has solutions a=\sqrt{2}+1, \;\ a=1-\sqrt{2}

    b(\sqrt{2}+1)^{n}+c(1-\sqrt{2})^{n}

    Use the initial conditions to solve:

    1=b(\sqrt{2}+1)+c(1-\sqrt{2})

    1=b(\sqrt{2}+1)^{2}+c(1-\sqrt{2})

    Solve the system and get b=\frac{\sqrt{2}-1}{2}; \;\  c=\frac{-(\sqrt{2}+1)}{2}

    Therefore, we have:

    a_{n}=(\frac{\sqrt{2}-1}{2})(\sqrt{2}+1)^{n}+(\frac{-(\sqrt{2}+1)}{2})(1-\sqrt{2})^{n}

    Now, perhaps you can use this to prove the solutions are always odd.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    a_1=1; a_2=1 and a_n=2\cdot{a_{n-1}}+a_{n-2}

    We have the base cases, so we'll go to the inductive step

    Suppose a_{n-1} and a_{n-2} are odd, we shall prove that a_n is also odd

    Indeed, a_n=2\cdot{a_{n-1}}+a_{n-2}\equiv{2\cdot{1}+1}\equiv{1}(\bmod.{2})

    Or if you prefer: a_{n-1}=2a+1 and a_{n-2}=2b+1 ( a and b are natural numbers)

    So a_n=2\cdot{(2a+1)}+2b+1=2(2\cdot{a}+b+1)+1 an odd number
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 01:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 19th 2010, 06:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  5. induction
    Posted in the Algebra Forum
    Replies: 3
    Last Post: June 18th 2008, 06:22 AM

Search Tags


/mathhelpforum @mathhelpforum