1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof By Induction

  1. Oct 5, 2009 #1
    1. The problem statement, all variables and given/known data
    http://img10.imageshack.us/img10/8418/56729818.gif [Broken]


    3. The attempt at a solution

    Firstly do I need to use the "simple induction" or "complete induction"?

    I will try the simple induction.

    Base Case: [tex]P(1) = f_1 f_0 - f_{1}^2 = (-1)^1[/tex]

    We don't know what the value of [tex]f_0[/tex] is, but if [tex]f_0 = 0[/tex] we get [tex]1 .0 - 1=-1[/tex]. Therefore P(1) is true.

    Inductive Step: Suppose P(k) is true, where [tex]k \in N[/tex]. Now I'm stuck & don't know how to deduce that P(k+1) is true.

    i.e. show that [tex]P(k+1) = f_{k+1}.f_k - f^2_{k+1}=(-1)^{k+1}[/tex] is true.

    any help or clues here is very appreciated :smile:
     
    Last edited by a moderator: May 4, 2017
  2. jcsd
  3. Oct 5, 2009 #2

    lanedance

    User Avatar
    Homework Helper

    i think you may have to extend it a bit, show P(1) & P(2) true, then assume P(n) & P(n-1) now try and show P(n+1)
     
  4. Oct 5, 2009 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    There is NO "[itex]f_0[/itex]". Your base case is [itex]f_3f_1- f_2^2= (-1)^2[/quote]

    [/quote]Inductive Step: Suppose P(k) is true, where [tex]k \in N[/tex]. Now I'm stuck & don't know how to deduce that P(k+1) is true.

    i.e. show that [tex]P(k+1) = f_{k+1}.f_k - f^2_{k+1}=(-1)^{k+1}[/tex] is true.

    any help or clues here is very appreciated :smile:[/QUOTE]
    You are writing the formula incorrectly: it is NOT "[itex]P(k+1) = f_{k+1}.f_k - f^2_{k+1}=(-1)^{k+1}[/itex]", it is [itex]f_{k+2}f_{k}- f^2_{k+1}= (-1)^{k+1}[/itex]
     
    Last edited by a moderator: May 4, 2017
  5. Oct 8, 2009 #4
    Hi!

    Thanks, lanedance. We know that [tex]f_1 = f_2 =1[/tex] and using the given formula [tex]f_n = f_{n-1}+f_{n-2}[/tex] we find [tex]f_3 = 2[/tex].

    So the base case is:[tex]f_3 . f_1 - f_2 = (-1)^2[/tex]
    [tex]2.1-1=(-1)^2[/tex]
    Base case is true.

    Inductive step:
    Suppose P(k) is true for some [tex]k \in \mathbb{N}[/tex]
    Sorry Halls, it was a typo. I meant P(k+1) is [tex]f_{k+2}f_{k}- f^2_{k+1}= (-1)^{k+1} = (-1)^k .(-1)[/tex]

    Here's where I'm stuck. Any hints on how to prove P(k+1)?
     
  6. Oct 10, 2009 #5
    We know that [tex]f_{k+1}f_{k-1}- f^2_{k}= (-1)^{k}[/tex]

    I can simplify [tex]f_{k+2}f_{k}- f^2_{k+1}[/tex] to:

    [tex](f_{k+1}+f_k)f_{k}- f^2_{k+1}[/tex]

    Now how can we simplify this to show it equals to [tex](-1)^{k+1}[/tex] and finish the proof?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof By Induction
  1. Proof by induction (Replies: 2)

  2. Proof by induction (Replies: 9)

  3. Proof by induction (Replies: 32)

  4. Induction Proof (Replies: 14)

  5. Proof by Induction (Replies: 6)

Loading...