Es esta conjetura de Fibonacci sumas correctas?

Question

Tengo el siguiente conjetura, necesito saber una prueba sólo en el caso de la mina que está mal, o la conjetura es incorrecto.

La suma de $k$ distintos números de Fibonacci puede ser escrito en la mayoría de los $k$ formas como la suma de otro $k$ distintos números de la secuencia

Prueba: tomemos, por ejemplo 4, los números de Fibonacci, con distintos valores: $$144+34+3+2$$ Podemos ver que debemos mantener la distinción y el número de los números de Fibonacci. Así que cuando nos dividimos los números; $$[89+55]+[13+21]+3+2$$

Es inmediatamente evidente que si algunos de los números se dividen en pequeños números de Fibonacci, los demás deben ser combinadas para mantener a sólo 4 números. Así, el 3+2 es 5, y cualquiera de 144 o 34 mantenerse como está. Por lo tanto, $$144+34+3+2=89+55+34+5=144+21+13+5$$

Sé que es un rudimentario de prueba e $k$ maneras de escribir la misma suma es probablemente un mal límite superior, pero al menos por ahora funciona.

Por favor, hágamelo saber lo que está mal. Gracias.

Answer 1

Se demuestra que la conjetura límite superior de $k$ a una distancia considerable de la verdad.

Deje $W$ ser un conjunto de $3n$ distintos números de Fibonacci, de los cuales, $n$ son solitarios (ningún otro número de Fibonacci en $W$ está cerca de ellos) y el resto de $2n$ están solas parejas. Una solitaria pareja es un conjunto de dos números de Fibonacci consecutivos, con ningún otro elemento de $W$ cerca de ellos. Deje $N$ la suma de los números de Fibonacci en $W$.

A continuación, podemos obtener otra representación de $N$ como una suma de $3n$ números de Fibonacci mediante la selección de cualquiera de $k$ solitario números, y que representan a cada uno de ellos como una suma de dos números de Fibonacci consecutivos, y al seleccionar cualquiera $k$ solitario parejas, y que expresan cada uno de sus sumas como un solo número Fibonacci.

El $k$ solitario números puede ser elegido de la $n$ solitario números en $W$ $\binom{n}{k}$ maneras. Para cada elección, el $k$ solitario parejas puede ser elegido en $\binom{n}{k}$ maneras. De ello se desprende que $N$ tiene al menos $$\sum_{k=0}^n \binom{n}{k}\binom{n}{k}$$ representaciones como suma de los distintos números de Fibonacci. Es bien conocido que la suma es igual a $\binom{2n}{n}$. Para un gran $n$, esto es mucho más grande que el $3n$ que la conjetura podría sugerir. De hecho, mediante el uso de la fórmula de Stirling, uno puede mostrar que $\binom{2n}{n}$ es asintóticamente igual a $\sqrt{\frac{2}{\pi}}\frac{2^{2n}}{\sqrt{2n+1}}$.

Answer 2

Como regla general, usted querrá usar Zeckendorf del teorema para encontrar estas representaciones; se dice que cualquier número tiene una representación única como la suma de no consecutivos números de Fibonacci. André ha señalado que su conjetura es falsa en general, pero es posible encontrar un sencillo límite en el número de sumas posibles.

Digamos que usted desea escribir $k$ como la suma de $n$ números de Fibonacci, y el Zeckendorf del teorema de la suma contiene $m<n$ términos. De cualquier $n$-plazo de la suma que usted desea, usted será capaz de obtener la Zeckendorf suma varias veces la combinación de términos que hasta que no los términos restantes son consecutivos. Esto implica que usted puede conseguir cualquier $n$plazo suma a partir de la Zeckendorf suma y la división de los términos en ella hasta que llegues $n$ de ellos.

Digamos que usted comience con un solo plazo $F_a$. La única forma de división que es como $F_a=F_{a-1}+F_{a-2}$; la única manera de dividir , que es como $F_{a-1}+F_{a-3}+F_{a-4}$; y así sucesivamente, es decir, cualquier suma que comenzó como un solo número Fibonacci tiene más de una representación como la suma de $n$ distintos números de Fibonacci para cualquier $n$ (ya que en cada punto de los índices diferentes a la mayoría de los dos, la única división que es posible, trata de romper el menor número en la suma).

Por lo tanto, si usted comienza con un Zeckendorf suma que ha $m$ términos, su única decisión posible es cómo muchas veces la división de cada uno de esos términos; una vez que usted sabe que usted va a tener una única suma. (Puede ser que sus términos se "chocan" y usted no recibirá una suma de distintos números de Fibonacci, pero sin duda va a conseguir todo lo posible la suma de algunas de estas especificaciones, lo que nos lleva a una sobre cuenta.) Para obtener una $n$plazo suma, se debe dividir un total de $n-m$ veces. Por una de las estrellas-y-bares argumento, hay en la mayoría de las ${n-1 \choose m-1}$ maneras de hacer esto. Así reparado versión de su conjetura de que el estado:

Si el Zeckendorf suma de $k$ contiene $m$ términos, hay en la mayoría de las ${n-1 \choose m-1}$ formas de escritura $k$ como la suma de $n$ distintos números de Fibonacci.