What are $x$ and $y$ in $xF_n$ + $yF_{n-1}$ = $1$?

Question

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.

Answer 1

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)$

Answer 2

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.

Answer 3

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] $$

Answer 4

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) $$