# Euclidean Algorithm and Fibonacci proof!

1. Feb 29, 2012

### FelixHelix

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$_{n+1}$ is the first remainder equal to 0 in the Euclidean Algorithm then r$_{n+1-k}$ $\geq$ f$_{k}$

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.

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

2. Relevant equations

3. The attempt at a solution