Euclidean Algorithm and Fibonacci proof

[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.

Please help

Felix

 

[LightHero]

The proof by induction goes as follows: Base Step (n=1): Since the Euclidean Algorithm starts with two numbers, r_1 and r_0, the first remainder equal to 0 is r_1. Therefore, r_1-k = 0 for all values of k ≥ 1 and thus r_1-k ≥ f_k. Inductive Step: Assume that it is true for n=k, i.e., r_{k+1-k} ≥ f_k. Then, for n=k+1, we have r_{k+2-k} = r_{k+1} which is the first remainder equal to 0. Thus, r_{k+2-k}=r_{k+1} ≥ f_k, which proves the inductive step. Therefore, by induction, we can conclude that if r_{n+1} is the first remainder equal to 0 in the Euclidean Algorithm then r_{n+1-k} ≥ f_k.