2
$\begingroup$

We know that the $\gcd$ of consecutive Fibonacci numbers is $1$. But while finding the coefficients $x$ and $y$ in using euclidean algorithm in reverse direction I am not able to find any pattern so that I can write $x,y$ in terms of n.

$\endgroup$
3
$\begingroup$

You can show by induction that: $F_{n+1}F_{n-1}-F_nF_n=(-1)^{n-1}$ then your Bezout coefficient $a,b$ can be $(a,b)=(F_{n-1},F_n)$

$\endgroup$
2
$\begingroup$

These are the extended euclidean algorithm outputs for consecutive pairs of Fibonacci numbers:

 (1, 0, 1),
 (1, 1, 0),
 (1, -1, 1),
 (1, 2, -1),
 (1, -3, 2),
 (1, 5, -3),
 (1, -8, 5),
 (1, 13, -8),
 (1, -21, 13),
 (1, 34, -21),
 (1, -55, 34),
 (1, 89, -55),
 (1, -144, 89),
 (1, 233, -144),
 (1, -377, 233),
 (1, 610, -377),
 (1, -987, 610),

Hopefully, you can get your answer from here.

$\endgroup$
1
$\begingroup$

Hint:

Since $$ \left( {\matrix{ {F_{n + 1} } \cr {F_n } \cr } } \right) = \left( {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right)\left( {\matrix{ {F_n } \cr {F_{n - 1} } \cr } } \right) $$ then $$ 1 = \left( {\matrix{ {x_{n + 1} } & {y_{n + 1} } \cr } } \right)\left( {\matrix{ {F_{n + 1} } \cr {F_n } \cr } } \right) = \left( {\matrix{ {x_{n + 1} } & {y_{n + 1} } \cr } } \right)\left( {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right)\left( {\matrix{ {F_n } \cr {F_{n - 1} } \cr } } \right) = \left( {\matrix{ {x_n } & {y_n } \cr } } \right)\left( {\matrix{ {F_n } \cr {F_{n - 1} } \cr } } \right) $$

$\endgroup$
  • $\begingroup$ Essentially the same as I wrote, but without determinants. But I think using them makes it clearer. $\endgroup$ – Bill Dubuque Feb 9 at 17:34
  • $\begingroup$ @BillDubuque: sorry, I did not reload when posting my answer .. I would cancel mine, but to me it seems to provide a more explicit way. Do you mind if I leave it ? $\endgroup$ – G Cab Feb 9 at 18:24
  • $\begingroup$ @G.Cab The comment was meant merely to help readers understand the relationship between the answers. $\endgroup$ – Bill Dubuque Feb 9 at 20:03
0
$\begingroup$

Hint $ $ Take the determinant of the following matrix form of the fibonacci recurrence $$ \left[\begin{array}{ccc} \,1 & 1 \\\ 1 & 0 \end{array}\right]^{\large n} = \left[\begin{array}{ccc} F_{\large n+1} & F_{\large n} \\\ F_{\large n} & F_{\large n-1} \end{array}\right] $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.