Ile sposobów przedstawienia dowolnego N jako sumy liczb nieparzystych? [duplikować]

Nov 28 2020

Rozwiązałem kilka podstawowych problemów z kodowaniem matematycznym i znalazłem to dla dowolnej liczby $N$, liczbę sposobów wyrażania $N$ jako suma liczb nieparzystych to $Fib[N]$ gdzie $Fib$jest Fibonnaci, nie mam na to ważnego dowodu i nie rozumiem, jak można to rozwiązać za pomocą nawrotów. Czy ktoś może to zapewnić?
Jeśli nie otrzymujesz tego Załóżmy, że dla N = 4 liczba sposobów zapisania tego jako suma liczb nieparzystych wynosi 3, czyli Fibonnaci na$3$

$4=> 1+1+1+1$
$4=> 1+3$
$4=> 3+1$
UWAGA-> skład zamawiany $( 1+3)$ i $(3+1)$są różne . UPD -> nie twierdzę, że sam to zauważyłem, ale w rozwiązaniu problemu znalazłem to, poprosiłem o znalezienie ważnego dowodu / przyczyny

Odpowiedzi

9 Magma Nov 28 2020 at 04:05

Powiedzmy $S(n)$ to zbiór sposobów pisania $n$ jako suma liczb nieparzystych.

Możemy podzielić ten zestaw na dwa podzbiory: $A(n)$ i $B(n)$, gdzie $A(n)$ jest zbiorem sum, w których ostatnim szczytem jest a $1$, i $B(n)$ jest zbiorem wszystkich innych sum.

Czy widzisz dlaczego $A(n)$ ma taki sam rozmiar jak $S(n-1)$? Czy widzisz dlaczego$B(n)$ ma taki sam rozmiar jak $S(n-2)$?

Jeśli to udowodnisz, znajdziesz to $|S(n)| = |A(n)| + |B(n)| = |S(n-1)| + |S(n-2)|$, czyli relacja rekurencji Fibonacciego. Następnie możesz udowodnić przez indukcję, że twój ciąg jest równy ciągowi Fibonacciego.

4 MarkoRiedel Nov 28 2020 at 04:11

Od początku kierujemy się zasadą, że liczba kompozycji w częściach nieparzystych jest określona przez

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

Upraszcza to

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

Teraz $$F(z) = \frac{z}{1-z-z^2}$$ jest OGF liczb Fibonacciego i mamy roszczenie.