Page 2 of 2 FirstFirst 12
Results 16 to 20 of 20

Math Help - Proof by induction

  1. #16
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    You are doing it correctly, but you need to manipulate that fibonacci expression. You can do that by looking at the non-inductive proof I gave. And following with the same reasoning.
    Follow Math Help Forum on Facebook and Google+

  2. #17
    Senior Member
    Joined
    Apr 2006
    Posts
    290
    Quote Originally Posted by ThePerfectHacker
    You are doing it correctly, but you need to manipulate that fibonacci expression. You can do that by looking at the non-inductive proof I gave. And following with the same reasoning.
    I'm so rubbish at the induction proof. Could someone just show me what I need to do? It's due in for tomorrow please
    Follow Math Help Forum on Facebook and Google+

  3. #18
    Senior Member
    Joined
    Apr 2006
    Posts
    290
    Is this better???

    Step 1: For n = 1, we have


    (F_1 \cdot F_{1+2}) - (F_{1+1})^2 = (-1)^{1+1} = 1


    Hence the equation holds for n = 1

    Step 2: Assume the equation is true for n = k (inductive hypothesis), we have:

    (F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}

    Step 3: We then have to use our inductive hypothesis to prove that the statement is also true for n = k + 1, i.e we have to prove:

    (F_{k+1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}

    Since there is a k\geq 2 such as,
    F(k)^2-F(k+1)F(k-1)=(-1)^{k-1}
    Then proof it hold for k+1. But the expression,
    F(k+1)^2-F(k+2)F(k)=(-1)(F(k)^2-F(k+1)F(k-1))
    But,
    F(k)^2-F(k+1)(k-1)=(-1)^{k-1}
    Thus,
    F(k+1)^2-F(k+1)F(k)=(-1)(-1)^{k-1}=(-1)^k
    Thus, it hold true for k+1.

    (F_{k+1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}

    Hence the equation holds true for n = k + 1
    Follow Math Help Forum on Facebook and Google+

  4. #19
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Natasha1
    Is this better???

    Step 1: For n = 1, we have


    (F_1 \cdot F_{1+2}) - (F_{1+1})^2 = (-1)^{1+1} = 1


    Hence the equation holds for n = 1

    Step 2: Assume the equation is true for n = k (inductive hypothesis), we have:

    (F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}

    Step 3: We then have to use our inductive hypothesis to prove that the statement is also true for n = k + 1, i.e we have to prove:
    F_{k+1} F_{k+3} - (F_{k+2})^2 = F_{k+1} (F_{k+2}+F_{k+1}) - (F_{k+2})^2

    =F_{k+1} F_{k+2}+(F_{k+1})^2 - (F_{k+2})^2.

    Now:

    F_{k+1}=F_{k+2}-F_{k},

    so:

    F_{k+1} F_{k+3} - (F_{k+2})^2= (F_{k+2}-F_{k}) F_{k+2}+(F_{k+1})^2 - (F_{k+2})^2

    =-F_{k} F_{k+2}+(F_{k+1})^2=-1((F_k \cdot F_{k+2}) - (F_{k+1})^2)=(-1)^{k+2}
    .

    Which proves that if the statement is true for k it is true for
    k+1.

    RonL
    Last edited by CaptainBlack; May 29th 2006 at 02:04 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #20
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,912
    Thanks
    775
    Hello, Natasha!

    An inductive proof requires some world-class acrobatics . . .


    I need to prove by induction that for the Fibonacci sequence:

    (F_n)\cdot(F_{n+2}) - (F_{n+1})^2 \;= \;(-1)^{n+1} . . . F_n being a Fibonacci number

    Verify -1)^2\quad\Rightarrow\quad 1\cdot2 - 1^2\:=\:1" alt="S(1):\;\;(F_1)\cdot(F_3) - (F_2)^2 \:=\-1)^2\quad\Rightarrow\quad 1\cdot2 - 1^2\:=\:1" /> . . . yes!


    Assume S(k) is true: . (F_k)(F_{k+2}) - (F_{k+1})^2\;=\;(-1)^{k+1}

    . . and we will try to prove F_{k+1})(F_{k+3}) - (F_{k+2})^2\:=\-1)^{k+2} " alt="S(k+1)\:=\F_{k+1})(F_{k+3}) - (F_{k+2})^2\:=\-1)^{k+2} " />


    Since F_k\,=\,F_{k+2} - F_{k+1} and F_{k+2} \,=\,F_{k+3} - F_{k+1}

    S(k) becomes: (F_{k+2} - F_{k+1})(F_{k+3} - F_{k+1}) - (F_{k+1})^2 \;= \;(-1)^{k+1}


    Expand: (F_{k+2})(F_{k+3}) - (F_{k+1})(F_{k+2}) - (F_{k+1})(F_{k+3}) + (F_{k+1})^2 - (F_{k+1})^2\;=\;(-1)^{k+1}


    We have: (F_{k+2})(F_{k+3}) - (F_{k+1})(F_{k+2}) - (F_{k+1})(F_{k+3}) \;= \; (-1)^{k+1}


    Factor: (F_{k+2})\cdot(\underbrace{F_{k+3} - F_{k+1}}) - (F_{k+1})(F_{k+3}) \;= \; (-1)^{k+1}
    . . . . . . . . . . .This is F_{k+2}

    An we have: (F_{k+2})^2 - (F_{k+1})(F_{k+3}) \;=\;(-1)^{k+1}


    Multiply by -1:\;\;(F_{k+1})(F_{k+3}) - (F_{k+2})^2\;=\;(-1)^{k+2}

    . . . ta-DAA! . . . This is S(k+1)\;!

    Follow Math Help Forum on Facebook and Google+

Page 2 of 2 FirstFirst 12

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 08:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 01:09 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 04:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM

Search Tags


/mathhelpforum @mathhelpforum