Cada número natural puede ser escrito como la suma de los distintos números de Fibonacci?

Question

Puede alguien sugerencia me a probar:

$\forall n\in \mathbb{N}: \exists$ Números de Fibonacci $ F_{i_1},\ldots,F_{i_k}$ tal forma que: $$\sum F_{i_k}=n$$

Nota: Cada número de Fibonacci sólo puede aparecer una vez. Gracias

Answer 1

De hecho, todo entero positivo puede escribirse de forma única como suma de una o más no consecutivos números de Fibonacci; esto se conoce un Zeckendorf del teorema. Hay incluso un simple algoritmo para encontrar esta representación: sólo tiene que utilizar el algoritmo voraz, siempre recogiendo el mayor número Fibonacci que todavía 'fit'. E. g., $32=21+8+3$. Este hecho debe sugieren que una prueba por inducción podría funcionar: si $n$ no es un número de Fibonacci, y $F_k$ es el mayor número Fibonacci menos de $n$, ver el $n-F_k$.

Demostrar la singularidad (lo cual es cierto sólo con la restricción de que los números de Fibonacci se utiliza ser no consecutivos) toma un poco más de trabajo, y en cualquier caso de que no se les preguntó a hacerlo. Aún así, puede que le resulte interesante a tratar. Usted también puede encontrar algunas de las probabilidades y termina aquí interesante.

Answer 2

Sugerencia: Inducción! (Inicio de $n=4$)