Podział liczby

[cis123]

Niech \(\displaystyle{ P(n)}\) będzie zbiorem uporządkowanych podziałów liczby \(\displaystyle{ n}\), czyli ciągów \(\displaystyle{ a = <a_{1}, a_{2}, ...>}\) dodatnich liczb całkowitych takich, że \(\displaystyle{ a_{1} + a_{2} + ... = n}\), i niech \(\displaystyle{ f(a) = a_{1} * a_{2} * ...}\) będzie iloczynem składników takiego podziału.

Udowodnij, że \(\displaystyle{ \sum_{a \in P(n)}^{} f(a) = F_{2n}}\) , gdzie \(\displaystyle{ F_{n}}\) oznacza n-tą liczbę Fibonacciego.
WSKAZÓWKA: Niech \(\displaystyle{ a'}\) oznacza podział powstający z \(\displaystyle{ a}\) przez zastąpienie ostatniego składnika jedynką. Rozważ \(\displaystyle{ \sum_{a \in P(n)}^{} f(a')}\).

Jakieś pomysły?

[Mruczek]

To zadanie nr 2 z egzaminu z MD dla informatyki na MIMUW w 2016 r.,
rozwiązanie tutaj:

Kod: Zaznacz cały

http://wakacjezmd.github.io/2016/egzamin/1/