¿Pregunta no trivial sobre los números de Fibonacci?

Question

Estoy buscando una pregunta no trivial, pero no superdifícil, relativa a los números de Fibonacci. Debe ser de un nivel adecuado para un curso de grado.

Aquí hay un ejemplo (no tan bueno) del tipo de cosas que estoy buscando.

a) Demuestre que todo número entero positivo puede representarse en binario sobre la base de los números de Fibonacci. Es decir, demuestre que para todo $n$ existen bits $x_1,\ldots,x_k$ tal que $n = \sum_{i=1}^kx_iF_i$ .

b) Dé un algoritmo para incrementar dichos números en tiempo amortizado constante.

¿Alguna idea para mejorarlas?

Answer 1

Tengo cierta predilección por un artículo que escribimos mi director de tesis y yo. Se puede encontrar en http://www.tylerclark12.com/Portfolio/Math/FibQuarterly.pdf . Es posible que no pueda utilizar todo el contenido del documento para su clase, pero estoy seguro de que podría utilizar parte de él. Hágame saber si puedo ayudarle en algo más.

Answer 2

1. Parametrización de la ecuación $x^2-xy-y^2=\pm1$ . El siguiente paso es un teorema de aislamiento bidimensional, véase Cassels, J. W. S. Introducción a la geometría de los números, sec. II. 4. Formas cuadráticas indefinidas .

2. El juego de Wythoff.

3. Otro buen juego es Fibonacci nim.

4. Método de Newton aplicado a $x^2-x-1=0$ con $x_0=0$ o $x_0=1.$

5. Para impar $p$ tenemos $F_n\left(U_{p-1}\left(\frac{\sqrt{5}}{2}\right)\right)=\frac{F_{np}}{F_p}$ , donde $F_n(x)$ y $U_n(x)$ son los polinomios de Fibonacci y Tchebyshev.

6. Fracción continua de Niza (véase la fórmula (6.143) de Matemáticas concretas ) $$\frac{z^{F_1}}{1+\frac{z^{F_2}}{1+\frac{z^{F_3}}{1+\frac{z^{F_4}}{1+\ldots}}}}=(1-z)\sum_{n\ge 1}z^{[n\varphi]}.$$

Answer 3

Se trata de una generalización de los números clásicos de Fibonacci que abre muchas facetas de propiedades heredadas. Definir $\{0\}_{s,t}=0, \{1\}_{s,t}=1$ y para $n\geq2$ , $$\{n\}_{s,t}=s\{n-1\}_{s,t}+t\{n-2\}_{s,t}.$$ Aquí $s$ y $t$ pueden tratarse como variables o como números. Para simplificar, escriba $\{n\}$ para $\{n\}_{s,t}$ . Los primeros valores son: $$\{2\} = s, \qquad \{3\} = s^2 + t, \qquad \{4\}= s^3 + 2st, \qquad \{5\} = s^4 + 3s^2t + t^2.$$ Si $s=2, t=-1$ entonces $\{n\}=n$ los enteros habituales. Si $s=q+1, t=-q$ obtenemos la norma $q$ -análogos de los números enteros $$\{n\}=1+q+\cdots+q^{n-1}=[n]_q.$$ Tras estas introducciones, se generalizan varios resultados clásicos. Por ejemplo (véase el corolario 2.6 en la referencia siguiente para una prueba probabilística) $$\sum_{n=0}^{\infty}\frac{t\{n\}_{s,t}}{(s+t)^{n+1}}=\frac1{s+t-1}$$ generaliza (poner $s=t=1$ ) $$\sum_{n=0}^{\infty}\frac{F_n}{2^{n+1}}=1.$$ Puede elegir y escoger resultados adicionales de http://arxiv.org/pdf/1306.6511.pdf

Answer 4

$\bullet~~$ Si $x^2=x+1$ , $n\ge 2$ entonces tenemos $x^n=F_nx+F_{n-1}$ , donde $F_n$ es el $n^{th}$ Número de Fibonacci.

$\bullet~~\sum_{i=2}^{n} \tau^i+(1-\tau)^i =3(F_{n+1}-1)$ donde $F_n$ es el $n$ número de Fibonacci y $\tau$ es la proporción áurea. Se deduce de la identidad indicada en el Correo electrónico: por David.

Aquí puede obtener una prueba completa para ambos.

$\bullet~~$ Recientemente he encontrado una versión generalizada para Teorema de Cesaro [ teorema nº 81 ] en los números de Fibonacci. Afirma que - para un número fijo $p$ , $$\sum_{k=1}^{n}\dbinom{n}{k}F_p^kF_{p-1}^{n-k}F_k=F_{pn}.$$ Puede obtener una prueba completa en Número 3, Reflexiones matemáticas, 2018 (página 16).

Answer 5

"Una prueba combinatoria para la expresión no recursiva del polinomio de Fibonacci"

Una de las extensiones más conocidas de la sucesión de Fibonacci es el polinomio de Fibonacci que se define por la siguiente relación de recurrencia $$ F_n(x)=xF_{n-1}(x)+F_{n-2}(x)\, . $$ Una expresión no recursiva para $F_n(x)$ , dado en la siguiente forma

$$ F_n(x)=\sum_{j=0}^{\lfloor \frac{n-1}{2} \rfloor} \left( \begin{array}{c} n-j-1 \\ j \end{array} \right) x^{n-2j-1} \, . $$ Ahora, quiero demostrar la fórmula anterior con el método combinatorio. Supongamos la siguiente matriz $$ A_2=\left( \begin{array}{cc} x & 1 \\ 1 & 0 \end{array} \right) \, . $$ Con la inducción en $n$ podemos demostrar que el $n$ potencia de la matriz $A_2$ es el siguiente $$ A_2^n=\left( \begin{array}{cc} F_{n+1}(x) & F_{n}(x) \\ \\ F_{n}(x) & F_{n-1}(x) \end{array} \right) \, . $$ Supongamos que la matriz $A_p$ de orden $p$ sea de la siguiente forma

$$ A_p=\left( \begin{array}{cccccc} u_1 &u_2 &\cdots& \cdots &u_{p-1} &u_p \\ 1 &0 &\cdots &\cdots &\cdots &0 \\ 0 &\ddots &\ddots &\ddots &\ddots &\vdots \\ \vdots &\ddots &\ddots &\ddots &\ddots &\vdots \\ \vdots &\ddots &\ddots &\ddots &\ddots &\vdots \\ 0 &\cdots &\cdots &0 &1 &0 \\ \end{array} \right)_{p \times p} \, . $$ Tenemos el siguiente teorema combinatorio de Chen sobre el $(i,j)$ entrada de la $n$ potencia de la matriz $A_p$ , como se muestra

Que el $(i,j)$ entrada de la $n$ potencia de la matriz $A_p$ llamado $a_{ij}^n$ entonces la forma cerrada combinatoria de $a_{ij}^n$ , tiene la siguiente forma $$ a_{ij}^n=\sum_{(k_1,k_2,\cdots,k_p)} \frac{k_j+k_{j+1}+\cdots+k_p}{k_1+k_2+\cdots+k_p}\times \left( \begin{array}{c} k_1+\cdots+k_p \\ k_1,\cdots , k_p \end{array} \right) u_1^{k_1}\cdots u_p^{k_p} \, . $$ donde la suma es sobre enteros no negativos que satisfacen $$ k_1+2\, k_2+3\, k_3+\cdots + p\, k_p=n-i+j \, . $$ y los coeficientes $k_i$ se definen $1$ cuando $n=i-j$ . $$

Basado en el teorema de Chen la forma cerrada combinatoria de $F_n(x)$ es de la siguiente forma (nótese que a la posición de $F_n(x)$ en la matriz $A_2^n$ )

$$ F_n(x)=\sum_{(k_1,k_2)} \left( \begin{array}{c} k_1+k_2 \\ k_1, k_2 \end{array} \right) x^{k_1} \, . $$

donde la suma es sobre enteros no negativos que satisfacen $$ k_1+2\, k_2=n-1\, . $$

de la última relación, obtenemos las dos ecuaciones siguientes

$$ k_1+2\, k_2=n-1 \quad \Longrightarrow \left\{ \begin{array}{cc} 1) & k_1+k_2=n-k_2-1 \, ,\\ \\ 2) & k_1=n-2k_2-1 \, . \end{array} \right. $$

utilizando las dos ecuaciones anteriores, tenemos

$$ F_n(x)=\sum_{k_2} \left( \begin{array}{c} n-k_2-1 \\ n-2k_2-1, k_2 \end{array} \right) x^{n-2k_2-1} \, . $$

para simplificar, denote $k_2$ por $j$ entonces reescribimos la relación anterior, como sigue

$$ F_n(x)= \sum_{j=0}^{\lfloor \frac{n-1}{2} \rfloor} \left( \begin{array}{c} n-j-1 \\ n-2j-1 , j \end{array} \right) x^{n-2j-1} =\sum_{j=0}^{\lfloor \frac{n-1}{2} \rfloor} \left( \begin{array}{c} n-j-1 \\ j \end{array} \right) x^{n-2j-1} \, . $$

Artículo de Chen: http://www.sciencedirect.com/science/article/pii/0024379595901639