Nombre de façons de représenter n'importe quel N comme somme de nombres impairs? [dupliquer]
Je résolvais un problème de codage mathématique de base et j'ai trouvé que pour n'importe quel nombre $N$, le nombre de façons d'exprimer $N$ car la somme des nombres impairs est $Fib[N]$ où $Fib$est Fibonnaci, je n'ai pas de preuve valable pour cela et je n'ai pas compris que comment cela peut être résolu en utilisant des récurrences Quelqu'un peut-il fournir?
Si vous ne l'obtenez pas, Supposons que pour N = 4, le nombre de façons de l'écrire sous forme de somme de nombres impairs est de 3, ce qui correspond à Fibonnaci$3$
$4=> 1+1+1+1$
$4=> 1+3$
$4=> 3+1$
NOTE-> la composition est commandée $( 1+3)$ et $(3+1)$sont différents . UPD -> Je ne prétends pas que je l'ai observé moi-même mais dans la solution du problème je l'ai trouvé, j'ai demandé simplement de trouver une preuve / raison valable
Réponses
Disons $S(n)$ est l'ensemble des manières d'écrire $n$ comme une somme de nombres impairs.
Nous pouvons partitionner cet ensemble en deux sous-ensembles: $A(n)$ et $B(n)$, où $A(n)$ est l'ensemble des sommes où la dernière sommation est un $1$, et $B(n)$ est l'ensemble de toutes les autres sommes.
Pouvez-vous voir pourquoi $A(n)$ a la même taille que $S(n-1)$? Pouvez-vous voir pourquoi$B(n)$ a la même taille que $S(n-2)$?
Si vous le prouvez, vous trouvez que $|S(n)| = |A(n)| + |B(n)| = |S(n-1)| + |S(n-2)|$, qui est la relation de récurrence de Fibonacci. Vous pouvez alors prouver par récurrence que votre séquence est égale à la séquence de Fibonacci.
Nous avons des premiers principes que le nombre de compositions en parties impaires est donné par
$$[z^N] \sum_{q\ge 1} \left(\frac{z}{1-z^2}\right)^q.$$
Cela simplifie à
$$[z^N] \frac{z/(1-z^2)}{1-z/(1-z^2)} = [z^N] \frac{z}{1-z-z^2}.$$
Maintenant $$F(z) = \frac{z}{1-z-z^2}$$ est l'OGF des numéros de Fibonacci et nous avons la réclamation.