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!

Euclidean Algorithm and Fibonacci proof!

  1. Feb 29, 2012 #1
    Stuck on this CW question. have been learing about Eulcidean Algorithm and Bezouts Identity but I'm at a complete loss.

    Q: Prove by induction that if r[itex]_{n+1}[/itex] is the first remainder equal to 0 in the Euclidean Algorithm then r[itex]_{n+1-k}[/itex] [itex]\geq[/itex] f[itex]_{k}[/itex]

    I know that proof by induction starts with a base step with n = 1; leading to the inductive step on n+1 but I'm struggling to even understand the question properly.

    Any advice at all would be appreciated. The work is due in the morning :( and I can't find any examples like this on the web.

    Please help

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



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?



Similar Discussions: Euclidean Algorithm and Fibonacci proof!
  1. Dijkstra's Algorithm (Replies: 0)

Loading...