Results 1 to 3 of 3

Thread: Induction!

  1. #1
    Mar 2008


    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.

    Follow Math Help Forum on Facebook and Google+

  2. #2
    Eater of Worlds
    galactus's Avatar
    Jul 2006
    Chaneysville, PA
    The characteristic equation is $\displaystyle a^{2}-2a-1=0$

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

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

    Use the initial conditions to solve:

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

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

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

    Therefore, we have:

    $\displaystyle 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
    Oct 2007
    $\displaystyle a_1=1$; $\displaystyle a_2=1$ and $\displaystyle a_n=2\cdot{a_{n-1}}+a_{n-2}$

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

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

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

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

    So $\displaystyle 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: Apr 21st 2011, 12:36 AM
  2. Replies: 10
    Last Post: Jun 29th 2010, 12:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Apr 19th 2010, 05:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 09:33 PM
  5. induction
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Jun 18th 2008, 05:22 AM

Search Tags

/mathhelpforum @mathhelpforum