¿De cuántas maneras es posible escribir un número como la suma ordenada de $1$ y $2$

Question

¿De cuántas maneras es posible escribir un número como la suma ordenada de $1$ y $2$ .

Mirando los primeros enteros (positivos):

$1: (1) \to 1\ \text{ways}$

$2: (1,1), (2) \to 2\ \text{ways}$

$3: (1,1,1), (2,1), (1,2) \to 3\ \text{ways}$

$4: (1,1,1,1), (2,1,1), (1,2,1), (1,1,2), (2,2) \to 5\ \text{ways}$

Si $Q_n$ denota el número que necesitamos para encontrar el número de sumas ordenadas de, entonces

$$Q_n = F_{n+1}$$

Donde $F_{n+1}$ denota el $n+1$ término de la Secuencia de Fibonacci.

¿Hay alguna prueba de ello?

Es evidente que si el número $m$ 2's y $r$ 1's dará ${m +r \choose m,r}$ diferentes sumas que dan $Q_n$ pero no tengo ni idea de cómo conectar esto con Fibonacci o si hay otra forma de demostrarlo.

Tal vez estoy tratando de reinventar la rueda.

Answer 1

Es una prueba relativamente sencilla. Sabemos que hay una forma de sumar 1 y 2 para llegar a 0, a saber $0=0$ . Así que $G_0 = 0$ . Algo similar ocurre con $G_1 = 1$ . Ahora supongamos que sabemos $G_{n-1}$ y $G_{n-2}$ . Para cada combinación representada en $G_{n-1}$ podemos sumar 1 para obtener combinaciones en $G_{n}$ . Del mismo modo, podemos añadir 2 a cada combinación en $G_{n-2}$ . Estas combinaciones son distintas ya que suman números diferentes. Por lo tanto, $G_n = G_{n-1} + G_{n-2}$ La misma relación de recurrencia que tienen los números de Fibonacci. Como $G_0 = G_1 = 1$ , los mismos valores iniciales de la secuencia de Fibonacci, sabemos que las secuencias serán idénticas.

Answer 2

Podemos demostrarlo con una prueba directa.

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)$ . Entonces, construimos $Q(n+1)$ de esta manera:

1. 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$ .
2. 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.