Número de maneiras de representar qualquer N como soma de números ímpares? [duplicado]

Question

Eu estava resolvendo alguns problemas básicos de codificação matemática e descobri que para qualquer número $N$, o número de maneiras de expressar $N$ como a soma dos números ímpares é $Fib[N]$ Onde $Fib$é Fibonnaci, não tenho uma prova válida para isso e não entendi como isso pode ser resolvido com recorrências Alguém pode me fornecer?
Se você não está entendendo Suponha que para N = 4 um número de maneiras de escrevê-lo como a soma dos números ímpares é 3 que é Fibonnaci em$3$

$4=> 1+1+1+1$
$4=> 1+3$
$4=> 3+1$
NOTA-> a composição está ordenada $( 1+3)$ e $(3+1)$são diferentes . UPD -> Eu não afirmo que eu mesmo observei, mas na solução do problema eu encontrei, pedi apenas para encontrar alguma prova / razão válida para isso

Answer 1

Digamos $S(n)$ é o conjunto de maneiras de escrever $n$ como uma soma de números ímpares.

Podemos particionar este conjunto em dois subconjuntos: $A(n)$ e $B(n)$, Onde $A(n)$ é o conjunto de somas onde a última soma e é um $1$e $B(n)$ é o conjunto de todas as outras somas.

Você pode ver porque $A(n)$ tem o mesmo tamanho que $S(n-1)$? Você pode ver porque$B(n)$ tem o mesmo tamanho que $S(n-2)$?

Se você provar isso, você descobrirá que $|S(n)| = |A(n)| + |B(n)| = |S(n-1)| + |S(n-2)|$, que é a relação de recorrência de Fibonacci. Você pode então provar por indução que sua sequência é igual à sequência de Fibonacci.

Answer 2

Temos desde os primeiros princípios que o número de composições em partes ímpares é dado por

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

Isso simplifica para

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

Agora $$F(z) = \frac{z}{1-z-z^2}$$ é o OGF dos números de Fibonacci e nós temos a reivindicação.