El orden de los números sí importa, lo que significa que para $k=4$ $4= 1+1+1+1,1+1+2,1+2+1,2+1+1,2+2$ Lo he calculado hasta $k=6$ y consigo que el número de los cálculos válidos sean: $1,2,3,5,8,13$ . Supongo que se trata de los números de Fibonacci, pero ¿de qué manera puedo demostrarlo?
Respuesta
¿Demasiados anuncios?
Podemos demostrarlo mediante una prueba directa. En primer lugar, dejamos que $Q(k)$ sea el número de formas en que un número $k$ se escribe como una suma de 1s y 2s.
Hipótesis: Para el número de Fibbonaci $F_1=1, F_2=1, F_{n}=F_{n-1}+F_{n-2}$ , $Q(k)=F_{k+1}$
Decimos que hemos construido cada orden de $Q(n)$ . A continuación, construimos $Q(n+1)$ de esta manera:
- Para todos los pedidos, añadimos $+1$ para cambiar $n$ a $n+1$ . (Ahora hay $Q(n)$ números). Nota: todos los números que se construyen aquí terminan en $+1$ .
- Para todos los pedidos que terminan en $+1$ lo cambiamos por $+2$ . Demostraremos que el importe será $Q(n-1)$ para completar la prueba. Nota: todos los números que se construyen aquí terminan en $+2$ .
Se puede ver que al construir de esta manera contiene todos los órdenes.
Prueba del paso 2: Si construimos $Q(n)$ de la forma anterior, entonces todos los números terminados en $+1$ será la cantidad $Q(n-1)$ por el paso 1. anterior, y hemos terminado.
