Combinaciones lineales de números de Fibonacci (coeficientes enteros)

Question

Mientras trabajaba en el problema nº 2 del Proyecto Euler, me encontré con la necesidad de expresar $F_n$ como una combinación lineal de $F_{n-3}$ y $F_{n-6}$ . Esto es relativamente sencillo de hacer:

$$\begin{align} F_n &= F_{n-1}+F_{n-2}\\ &= F_{n-1}+F_{n-3}+F_{n-4}\\ &= F_{n-1}+F_{n-3}+F_{n-5}+F_{n-6}\\&= F_{n-2}+2F_{n-3}+F_{n-5}+F_{n-6}\\&= 3F_{n-3}+F_{n-4}+F_{n-5}+F_{n-6}\\&=4F_{n-3}+F_{n-6}\end{align}$$

Este argumento es ad hoc hasta el extremo, y me hizo plantearme una conjetura más general:

Conjetura . Sea $a,b<n$ y $a\neq b$ . Entonces $F_n = \lambda F_{n-a} + \kappa F_{n-b}$ para algunos $\lambda,\kappa\in\mathbb Z$ .

¿Es esto cierto? Si es así, ¿cómo se puede demostrar? Si no es así, ¿podemos incluir algunas hipótesis sobre $a$ y $b$ ¿eso lo hace cierto?

Answer 1

Tenga en cuenta que no siempre podemos hacer esto con coeficientes enteros. Por ejemplo, $$ F_{n}=\frac52F_{n-2}+\frac12F_{n-5}\tag{1} $$ y $$ F_{n}=\frac{13}3F_{n-3}-\frac23F_{n-7}\tag{2} $$

---

Podemos utilizar el hecho de que $$ \left(\frac{1\pm\sqrt5}2\right)^n=\frac1{2^n}\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}5^k\pm\frac{\sqrt5}{2^n}\sum_{k=0}^{\lfloor(n-1)/2\rfloor}\binom{n}{2k+1}5^k\tag{3} $$ para conseguir $$ \begin{align} F_n= &\frac{\sum\limits_{k=0}^{\lfloor(b-1)/2\rfloor}\binom{b}{2k+1}5^k} {\sum\limits_{k=0}^{\lfloor(b-a-1)/2\rfloor}\binom{b-a}{2k+1}5^k}\frac{F_{n-a}}{2^a}\\ &+\left[\sum_{k=0}^{\lfloor b/2\rfloor}\binom{b}{2k}5^k -\frac{\sum\limits_{k=0}^{\lfloor(b-1)/2\rfloor}\binom{b}{2k+1}5^k} {\sum\limits_{k=0}^{\lfloor(b-a-1)/2\rfloor}\binom{b-a}{2k+1}5^k} \sum_{k=0}^{\lfloor(b-a)/2\rfloor}\binom{b-a}{2k}5^k\right]\frac{F_{n-b}}{2^b}\tag{4} \end{align} $$ Por lo tanto, siempre hay una recurrencia con coeficientes racionales para cualquier $0\lt a\lt b$ .

---

Obsérvese que si dejamos que $\psi=-1/\phi$ entonces ambos $\phi$ y $\psi$ satisfacer $$ \begin{align} 0 &=(x^n-\phi^n)(x^n-\psi^n)\\ &=x^{2n}-(\phi^n+\psi^n)x^n+(\phi\psi)^n\\ &=x^{2n}-L_nx^n+(-1)^n\tag{5} \end{align} $$ donde $L_n$ es un Número Lucas . Por lo tanto, los números de Fibonacci satisfacen $$ F_n=L_kF_{n-k}-(-1)^kF_{n-2k}\tag{6} $$ Fijar $k$ y que $a_j=jk$ y $b_j=(j+1)k$ . Ecuación $(6)$ tiene coeficientes enteros para $a_1,b_1$ .

Ecuación $(6)$ dice que si tenemos coeficientes $\lambda_j,\kappa_j\in\mathbb{Z}$ para $a_j,b_j$ entonces $$ \begin{align} F_n &=\lambda_jF_{n-jk}+\kappa_jF_{n-(j+1)k}\\ &=(\lambda_jL_k+\kappa_j)F_{n-(j+1)k}-(-1)^k\lambda_jF_{n-(j+2)k}\\ &=\lambda_{j+1}F_{n-(j+1)k}+\kappa_{j+1}F_{n-(j+2)k}\tag{7} \end{align} $$ donde $\lambda_{j+1}=\lambda_jL_k+\kappa_j$ y $\kappa_{j+1}=(-1)^{k+1}\lambda_j$ son ambos enteros para $a_{j+1},b_{j+1}$ .

Tenga en cuenta que $b_j=(j+1)k=(j+1)(b_j-a_j)$ .

Utilizando $(6)$ y $(7)$ obtenemos una recurrencia con coeficientes enteros si $b-a\mid b$ .

En particular, teniendo en cuenta $k=b-a$ y $j=\frac{b}{b-a}-1$ tenemos $$ \begin{bmatrix}\lambda\\\kappa\end{bmatrix} =\begin{bmatrix}L_k&1\\(-1)^{k+1}&0\end{bmatrix}^j \begin{bmatrix}1\\0\end{bmatrix}\tag{8} $$ Since $\small\begin{bmatrix}2&1\\-1&-1\end{bmatrix}^2=\begin{bmatrix}3&1\\-1&0\end{bmatrix}$ podemos aplicar $(8)$ aunque $b-a=2$ cuando $b$ es impar. Nos ocupamos de esto en la siguiente sección.

---

Como anotado por achille hui , $b-a=2$ también permite $\lambda,\kappa\in\mathbb{Z}$ . Esto se desprende del caso $b-a=1$ .

Si aplicamos $(8)$ al caso $a=b-1$ obtenemos $$ \begin{align} F_n &=F_b F_{n-b+1}+F_{b-1}F_{n-b}\\ &=F_b(F_{n-b+2}-F_{n-b})+F_{b-1}F_{n-b}\\ &=F_b F_{n-b+2}+(F_{b-1}-F_b)F_{n-b}\\ &=F_b F_{n-b+2}-F_{b-2}F_{n-b}\tag{9} \end{align} $$ Así, para $a=b-2$ , $$ \begin{bmatrix}\lambda\\\kappa\end{bmatrix} =\begin{bmatrix}F_b\\-F_{b-2}\end{bmatrix}\tag{10} $$

---

Conclusión: La conjetura, tal y como está planteada, es falsa. Sin embargo, si $b-a\mid b$ o $b-a=2$ entonces hay $\lambda,\kappa\in\mathbb{Z}$ , dado en $(8)$ o $(10)$ para que $$ F_n=\lambda F_{n-a}+\kappa F_{n-b}\tag{11} $$

Answer 2

Obsérvese que para cualquier recurrencia (incluida la secuencia de Fibonacci) que tenga una solución $u_n=A\alpha^n+B\beta^n$ la ecuación $$\lambda u_{n-a}+\mu u_{n-b}=\lambda(A\alpha^{n-a}+B\beta^{n-a})+\mu(A\alpha^{n-b}+B\beta^{n-b})=A(\lambda \alpha^{-a}+\mu\alpha^{-b})\alpha^n+B(\lambda \beta^{-a}+\mu\beta^{-b})\beta^n=u_n$$ implica $$\lambda \alpha^{-a}+\mu\alpha^{-b}=1$$ y $$\lambda \beta^{-a}+\mu\beta^{-b}=1$$

Y, teniendo en cuenta $\alpha, \beta, a, b$ esto tiene una solución única para $\lambda, \mu$ excepto en los casos degenerados.

Answer 3

Supongamos que $0 < a < b$ la condición necesaria y suficiente para la existencia de $\lambda, \mu \in \mathbb{Z}$ tal que $$F_n = \lambda F_{n-a} + \mu F_{n-b},\quad\forall n \in \mathbb{Z}_{+}\tag{*1}$$ es $$b - a \le 2\quad\text{ or }\quad b - a = \gcd(a,b) > 2.$$

Dejemos que $\alpha = \frac{1+\sqrt{5}}{2}$ y $\beta = \frac{1 - \sqrt{5}}{2}$ tenemos el La fórmula de Binet para los números de Fibonacci:

$$F_n = \frac{\alpha^n - \beta^n}{\alpha - \beta}$$

Utilizando esta fórmula, es fácil resolver $\lambda, \mu$ y encontrar:

$$F_n = \frac{1}{F_{b-a}}\left(F_b F_{n-a} - (-1)^{b-a} F_a F_{n-b}\right)$$

Se sabe que la secuencia de Fibonacci es una secuencia de divisibilidad fuerte .
Para cualquier número entero positivo $p, q$ tenemos

$$p | q \implies F_p | F_q\quad\text{ and }\quad \gcd(F_p,F_q) = F_{\gcd(p,q)}$$

Lo que busca es esencialmente equivalente a encontrar $a,b$ tal que

$$F_{b-a} | F_a \;\land\; F_{b-a}|F_b\quad\iff\quad F_{b-a} | \gcd(F_a,F_b) \quad\iff\quad F_{b-a} | F_{\gcd(a,b)}$$

Desde $\gcd(a,b) \le b - a \implies F_{\gcd(a,b)} \le F_{b-a}$ y $F_k$ es estrictamente creciente cuando $k > 2$ la la última condición se cumple cuando y sólo cuando

$$b - a \le 2\quad\text{ or }\quad b - a = \gcd(a,b) > 2$$

Esto conduce a tres y sólo tres familias de soluciones para $(*1)$ . A saber,

1. $b-a = 1$

   • $F_n = F_{a+1}F_{n-a} + F_{a} F_{n-a-1}$

2. $b - a = 2$

   • $F_n = F_{a+2}F_{n-a} - F_{a} F_{n-a-2}$

3. $b - a = \gcd(a,b) > 2$ es decir, hay números enteros $c > 2, m > 0$ tal que

   • $F_n = \frac{F_{(m+1)c}}{F_c} F_{n-mc} - (-1)^c \frac{F_{mc}}{F_c} F_{n-(m+1)c}$

   Como caso especial de esto, si se toma $m = 1$ Esto lleva a

   • $F_n = L_c F_{n-c} - (-1)^c F_{n-2c}$

   donde $L_c = \frac{F_{2c}}{F_c} = \alpha^c + \beta^c$ es el número de Lucas.

Answer 4

Recuerda que los números de Fibonacci son los único secuencia que satisface la ecuación $F_{n+1}=F_n+F_{n-1}$ y las condiciones $F_0=0$ , $F_1=1$ . Ahora, consideremos la secuencia $G_n=aF_{n-s}+bF_{n-t}$ . Entonces es obvio que $G_n$ satisface la ecuación (lineal) $G_{n+1}=G_n+G_{n-1}$ ; para tener $G_n=F_n$ entonces sólo debemos satisfacer $G_0=aF_{-s}+bF_{-t}=0$ y $G_1=aF_{1-s}+bF_{1-t}=1$ . En notación matricial, es la condición de que $\left(\array{0\\1}\right)=\left(\array{F_{-s}&F_{-t}\\F_{1-s}&F_{1-t}}\right)\left(\array{a\\b}\right)$ . Pero ahora, suponiendo que la matriz $\left(\array{F_{-s}&F_{-t}\\F_{1-s}&F_{1-t}}\right)$ es invertible (más sobre esto en un momento), podemos reescribirlo como $\left(\array{a\\b}\right)=\left(\array{F_{-s}&F_{-t}\\F_{1-s}&F_{1-t}}\right)^{-1}\left(\array{0\\1}\right) =\dfrac1{F_{-s}F_{1-t}-F_{-t}F_{1-s}}\left(\array{F_{1-t}&-F_{-t}\\-F_{1-s}&F_{-s}}\right)\left(\array{0\\1}\right)$ .

Ahora, La identidad de d'Ocagne afirma que $F_mF_{n+1}-F_{m+1}F_n=(-1)^nF_{m-n}$ ; al conectar $m=-s$ , $n=-t$ encontramos que el determinante de nuestra matriz original $F_{-s}F_{1-t}-F_{-t}F_{1-s}$ es sólo $(-1)^{t-s}F_{t-s}$ es distinto de cero (y por tanto la matriz es invertible) siempre que $t\neq s$ (y el caso $t=s$ es claramente degenerado - la no invertibilidad allí dice que no podemos escribir $F_n$ en función únicamente de $F_{n-s}$ para cualquier $s$ ).

Finalmente, utilizando la identidad y multiplicando por la matriz inversa, obtenemos $a=\dfrac{-F_{-t}}{(-1)^{t-s}F_{t-s}}$ y $b=\dfrac{F_{-s}}{(-1)^{t-s}F_{t-s}}$ ; ya que $F_{-n}=(-1)^{n+1}F_n$ se pueden escribir como $$a=(-1)^s\dfrac{F_t}{F_{t-s}}$$ y $$b=-(-1)^t\dfrac{F_s}{F_{t-s}}$$ Ahora, podemos utilizar el propiedad de divisibilidad de los números de Fibonacci, lo que implica que para $n\gt 2$ , $F_n\mid F_m$ si $n\mid m$ . Esto implica que para $a$ y $b$ sean enteros, entonces (como otros han señalado) debemos tener $|t-s|\leq 2$ o $(t-s)\mid s$ (nótese que esto implica inmediatamente que $(t-s)\mid t$ y así, por supuesto $a$ es un número entero si $b$ es).