1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: 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

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

    2. Relevant equations

    3. The attempt at a solution
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted