Nを奇数の合計として表す方法の数は？[複製]
私はいくつかの基本的な数学コーディングの問題を解決していましたが、 $N$、表現する方法の数 $N$ 奇数の合計は $Fib[N]$ どこ $Fib$フィボナッチです、私はこれの有効な証拠を持っておらず、これが再発を使用してどのように解決できるかを理解していませんでした誰かがそれを提供できますか？
取得できない場合は、N = 4の場合、奇数の合計が3であるため、フィボナッチ数であると仮定します。$3$
$4=> 1+1+1+1$
$4=> 1+3$
$4=> 3+1$
注->構成は注文されます $( 1+3)$ そして $(3+1)$異なっています 。UPD->私はそれを自分で観察したとは主張しませんが、問題解決でそれを見つけました、私はそれに対するいくつかの有効な証拠/理由を見つけるように頼みました
回答
まあ言ってみれば $S(n)$ 書く方法のセットです $n$ 奇数の合計として。
このセットを2つのサブセットに分割できます。 $A(n)$ そして $B(n)$、 どこ $A(n)$ 最後の被加数がである合計のセットです $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)|$、これはフィボナッチの漸化式です。次に、帰納法によって、シーケンスがフィボナッチ数列と等しいことを証明できます。
第一原理から、奇数部分への構成の数は次の式で与えられます。
$$[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であり、主張があります。