विषम संख्या के योग के रूप में किसी भी एन का प्रतिनिधित्व करने के तरीकों की संख्या? [डुप्लीकेट]

Question

मैं कुछ बुनियादी गणित कोडिंग समस्या को हल कर रहा था और पाया कि किसी भी संख्या के लिए $N$व्यक्त करने के तरीकों की संख्या $N$ विषम संख्याओं का योग है $Fib[N]$ कहां है $Fib$Fibonnaci है, मेरे पास इसके लिए कोई वैध प्रमाण नहीं है और यह नहीं समझा कि पुनरावृत्ति का उपयोग करके इसे कैसे हल किया जा सकता है क्या कोई इसे प्रदान कर सकता है?
यदि आपको यह नहीं मिल रहा है तो मान लें कि N = 4 संख्याओं के लिए इसे विषम संख्या के योग के रूप में लिखना है 3 जो कि Fibonni at है$3$

$4=> 1+1+1+1$
$4=> 1+3$
$4=> 3+1$
नोट-> रचना का आदेश दिया गया है $( 1+3)$ तथा $(3+1)$कुछ अलग हैं । UPD -> मैं यह दावा नहीं करता कि मैंने इसे स्वयं देखा था लेकिन समस्या समाधान में मैंने इसे पाया, मैंने इसे केवल कुछ वैध प्रमाण / कारण खोजने के लिए कहा

Answer 1

हम कहते हैं $S(n)$ लिखने के तरीकों का एक सेट है $n$ विषम संख्याओं के योग के रूप में।

हम इस सेट को दो सबसेट में विभाजित कर सकते हैं: $A(n)$ तथा $B(n)$, कहां है $A(n)$ sums का सेट है जहां अंतिम सारांश है a $1$, तथा $B(n)$ अन्य सभी रकमों का समूह है।

क्या आप देख सकते हैं क्यों $A(n)$ जैसा आकार है $S(n-1)$? क्या आप देख सकते हैं क्यों$B(n)$ जैसा आकार है $S(n-2)$?

यदि आप यह साबित करते हैं, तो आप पाते हैं कि $|S(n)| = |A(n)| + |B(n)| = |S(n-1)| + |S(n-2)|$, जो फिबोनाची पुनरावृत्ति संबंध है। फिर आप इंडक्शन द्वारा साबित कर सकते हैं कि आपका अनुक्रम फाइबोनैचि अनुक्रम के बराबर है।

Answer 2

हमारे पास पहले सिद्धांत हैं कि विषम भागों में रचनाओं की संख्या कितनी है

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

यह सरल करता है

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

अभी $$F(z) = \frac{z}{1-z-z^2}$$ फाइबोनैचि संख्याओं का OGF है और हमारा दावा है।