¿Número de formas de representar cualquier N como suma de números impares? [duplicar]

Question

Estaba resolviendo un problema básico de codificación matemática y descubrí que para cualquier número $N$, la cantidad de formas de expresar $N$ como suma de números impares es $Fib[N]$ dónde $Fib$es Fibonnaci, no tengo una prueba válida para esto y no entendí cómo se puede resolver esto usando recurrencias ¿Alguien puede proporcionarlo?
Si no lo obtiene Suponga que para N = 4 el número de formas de escribirlo como suma de números impares es 3, que es Fibonnaci en$3$

$4=> 1+1+1+1$
$4=> 1+3$
$4=> 3+1$
NOTA-> la composición está ordenada $( 1+3)$ y $(3+1)$son diferentes . UPD -> No afirmo que lo haya observado yo mismo, pero en la solución del problema lo encontré, pedí encontrar una prueba / razón válida para ello

Answer 1

Digamos $S(n)$ es el conjunto de formas de escribir $n$ como una suma de números impares.

Podemos dividir este conjunto en dos subconjuntos: $A(n)$ y $B(n)$, dónde $A(n)$ es el conjunto de sumas donde el último sumando es un $1$y $B(n)$ es el conjunto de todas las demás sumas.

¿Puedes ver por qué? $A(n)$ tiene el mismo tamaño que $S(n-1)$? ¿Puedes ver por qué?$B(n)$ tiene el mismo tamaño que $S(n-2)$?

Si prueba esto, encontrará que $|S(n)| = |A(n)| + |B(n)| = |S(n-1)| + |S(n-2)|$, que es la relación de recurrencia de Fibonacci. Luego puede probar por inducción que su secuencia es igual a la secuencia de Fibonacci.

Answer 2

Tenemos desde los primeros principios que el número de composiciones en partes impares viene dado por

$$[z^N] \sum_{q\ge 1} \left(\frac{z}{1-z^2}\right)^q.$$

Esto simplifica a

$$[z^N] \frac{z/(1-z^2)}{1-z/(1-z^2)} = [z^N] \frac{z}{1-z-z^2}.$$

Ahora $$F(z) = \frac{z}{1-z-z^2}$$ es el OGF de los números de Fibonacci y tenemos el reclamo.