Demostrar que los números de Fibonacci no son un polinomio.

Question

Hace un tiempo me pidieron demostrar que no existe un polinomio $P$ en $\mathbb R$ tal que $P(i)=f_i$ para todo $i\geq0$. Intenté obtener una demostración lo más elegante posible y esto es lo que obtuve.

Sea $p(x)=a_nx^n+a_{n-1}x^{n-1}+\dots +a_1x+a_0$ . Construye los polinomios $p_1(x)=a_n(x-1)^n+a_{n-1}(x-1)^{n-1}+\dots +a_1(x-1)+a_0$ y $p_2(x)=a_n(x-2)^n+a_{n-1}(x-2)^{n-1}+\dots +a_1(x-2)+a_0$.

Entonces el polinomio $p-(p_1+p_2)$ tiene infinitas raíces ya que $p(i)=p_1(i)+p_2(i)$ para $i$ un entero $\ge 1$ debido a la recurrencia de Fibonacci. Por lo tanto tenemos $p_1+p_2=p$ ya que un polinomio no nulo de grado $n$ puede tener como máximo $n$ ceros.

Sin embargo $p_1+p_2$ tiene coeficiente principal $2a_n$. Así que no pueden ser iguales.

¿Qué opinas de mi demostración? ¿Puedes encontrar otras demostraciones? ¿Demostraciones más simples? ¿Demostraciones más complicadas? Cuanto menos convencionales, mejor. Aprecio las demostraciones que puedan parecer excesivas en la cantidad de teoría que utilizan, aunque solo si terminan rápidamente.

Muchas gracias.

Saludos

Answer 1

Tomar las diferencias sucesivas de un polinomio no nulo debería resultar en un polinomio del siguiente grado más pequeño. Es decir, si $p$ es de grado $n$, entonces $p(x)-p(x-1)$ debería ser de grado $n-1.

Pero si $p(i)$ da números de Fibonacci, entonces $p(i)-p(i-1)=p(i-2)$. Entonces $\deg p=\deg(p)-1$, una contradicción. (Esta es una versión diferente de tu argumento (que es genial) ya que preguntaste sobre alternativas.)

Answer 2

(Una variación de una respuesta eliminada:)

Cualquier secuencia polinómica tiene una función generadora racional de la forma $\frac{P(x)}{(1-x)^k}$. Esto se puede ver diferenciando repetidamente la serie geométrica.

La secuencia de Fibonacci tiene una función generadora $\frac{x}{1-x-x^2}$, que no tiene esta forma. Dado que las funciones generadoras son únicas, se sigue que la secuencia de Fibonacci no es polinómica.

Answer 3

Si consideramos las ratios de los números de Fibonacci, podemos encontrar una tasa de crecimiento rápida: $$\frac{F_{n+1}}{F_{n}} = \frac{F_{n} + F_{n-1}}{F_n} = 1 + \frac{F_{n-1}}{F_n}<2$$ y $$\frac{F_{n-1}}{F_{n}} = \frac{F_{n-1}}{F_{n-1}+F_{n-2}} > \frac{F_{n-1}}{2 F_{n-1}} = 1/2$$ lo que significa que $$1.5 < \frac{F_{n+1}}{F_n} < 2.$$ Por lo tanto, $(1.5)^n < F_n < 2^n$ para $n>1$, lo que significa que la tasa de crecimiento de los números de Fibonacci es exponencial.

Supongamos que $p(i)=F_i$ para algún polinomio (de grado $m$), entonces el polinomio se puede escribir como $$p(x) = a_m x^m + a_{m-1} x^{m-1} + \cdots + a_0.$$ Así que $$|F_n| = |p(n)| \le n^m \sum_{i=1}^m |a_m| := Cn^m.$$ Esto significa $$(1.5)^n < Cn^m$$ para todos los $n$.

Podemos demostrar que esta desigualdad no puede cumplirse para todos los $n$. Es más claro cuando se utilizan logaritmos: $$(1.5)^n < Cn^m$$ lo que significa $$n \ln(1.5) < \ln(C) + m \ln(n)$$ y $$\ln(1.5) < \frac{\ln(C)}{n} + m \frac{\ln(n)}{n}.$$ El término $\ln(C)/n$ tiende a cero a medida que $n \to \infty$ y lo mismo sucede con $\ln(n)/n$. Sin embargo, dado que $\ln(1.5) > 0$, esto es una contradicción.

Answer 4

Considera las diferencias repetidas. Es decir, escribe una fila $p(1),p(2),p(3),\ldots$ y luego en la siguiente fila las diferencias $p(2)-p(1),p(3)-p(2),p(4)-p(3),\ldots$ de la primera fila, luego en la tercera fila las diferencias de la segunda fila, y así sucesivamente. Debería ser bien conocido que una fila obtenida de un polinomio de grado $n$ produce valores de un polinomio de grado $n-1$ en la siguiente fila y así sucesivamente, por lo que eventualmente llegamos a una fila de grado $0$ (es decir, constante) y a partir de entonces a filas completamente nulas.

Sin embargo, si comenzamos con la secuencia de Fibonacci, la siguiente fila es la secuencia de Fibonacci (desplazada) y nunca obtendremos una fila completamente nula.

Answer 5

$F_1=1$ y $F_3=2$ por lo que su diferencia es impar.

Los polinomios tienen la propiedad $P(x+n)-P(x)$ es divisible por $n$, y en particular $P(x+2)-P(x)$ siempre es par.