Anzahl der Möglichkeiten, ein N als Summe ungerader Zahlen darzustellen? [Duplikat]
Ich habe ein grundlegendes Problem mit der mathematischen Codierung gelöst und festgestellt, dass für jede Zahl $N$, die Anzahl der Ausdrucksmöglichkeiten $N$ als Summe der ungeraden Zahlen ist $Fib[N]$ wo $Fib$ist Fibonnaci, ich habe keinen gültigen Beweis dafür und habe nicht verstanden, wie dies mit Wiederholungen gelöst werden kann. Kann jemand damit versorgen?
Wenn Sie es nicht erhalten Angenommen, N = 4 Anzahl von Möglichkeiten, es zu schreiben, da die Summe der ungeraden Zahlen 3 ist, was Fibonnaci ist$3$
$4=> 1+1+1+1$
$4=> 1+3$
$4=> 3+1$
HINWEIS-> Die Komposition ist bestellt $( 1+3)$ und $(3+1)$sind anders . UPD -> Ich behaupte nicht, dass ich es selbst beobachtet habe, aber in der Problemlösung, die ich gefunden habe, habe ich darum gebeten, nur einen gültigen Beweis / Grund dafür zu finden
Antworten
Sagen wir $S(n)$ ist die Art der Schreibweisen $n$ als Summe ungerader Zahlen.
Wir können diese Menge in zwei Teilmengen unterteilen: $A(n)$ und $B(n)$, wo $A(n)$ ist die Menge der Summen, bei denen der letzte Summand a ist $1$, und $B(n)$ ist die Menge aller anderen Summen.
Kannst du sehen warum? $A(n)$ hat die gleiche Größe wie $S(n-1)$? Kannst du sehen warum?$B(n)$ hat die gleiche Größe wie $S(n-2)$?
Wenn Sie dies beweisen, finden Sie das $|S(n)| = |A(n)| + |B(n)| = |S(n-1)| + |S(n-2)|$, das ist die Fibonacci-Wiederholungsrelation. Sie können dann durch Induktion beweisen, dass Ihre Sequenz der Fibonacci-Sequenz entspricht.
Wir haben nach ersten Prinzipien, dass die Anzahl der Kompositionen in ungerade Teile gegeben ist durch
$$[z^N] \sum_{q\ge 1} \left(\frac{z}{1-z^2}\right)^q.$$
Dies vereinfacht zu
$$[z^N] \frac{z/(1-z^2)}{1-z/(1-z^2)} = [z^N] \frac{z}{1-z-z^2}.$$
Jetzt $$F(z) = \frac{z}{1-z-z^2}$$ ist der OGF der Fibonacci-Zahlen und wir haben den Anspruch.