Banyaknya cara untuk merepresentasikan N apapun sebagai jumlah dari bilangan ganjil? [duplikat]
Saya sedang memecahkan beberapa Masalah Pengkodean Matematika dasar dan menemukan bahwa Untuk nomor apa pun $N$, sejumlah cara untuk mengekspresikan $N$ sebagai jumlah dari Angka Ganjil $Fib[N]$ dimana $Fib$itu Fibonnaci, saya tidak memiliki bukti yang valid untuk ini dan tidak mengerti bahwa bagaimana ini dapat diselesaikan dengan menggunakan pengulangan. Dapatkah seseorang menyediakannya?
Misalkan N = 4 banyaknya cara penulisannya sebagai penjumlahan Bilangan Ganjil 3 yaitu Fibonnaci pada$3$
$4=> 1+1+1+1$
$4=> 1+3$
$4=> 3+1$
CATATAN-> komposisi dipesan $( 1+3)$ dan $(3+1)$berbeda . UPD -> Saya tidak mengklaim bahwa saya mengamati sendiri tetapi dalam solusi masalah saya menemukannya, saya meminta untuk menemukan beberapa bukti / alasan yang valid untuk itu
Jawaban
Katakanlah $S(n)$ adalah seperangkat cara untuk menulis $n$ sebagai jumlah dari angka ganjil.
Kita dapat mempartisi set ini menjadi dua subset: $A(n)$ dan $B(n)$, dimana $A(n)$ adalah himpunan penjumlahan dimana sumand terakhir adalah a $1$, dan $B(n)$ adalah himpunan dari semua jumlah lainnya.
Bisakah kamu melihat mengapa $A(n)$ memiliki ukuran yang sama dengan $S(n-1)$? Bisakah kamu melihat mengapa$B(n)$ memiliki ukuran yang sama dengan $S(n-2)$?
Jika Anda membuktikan ini, Anda akan menemukannya $|S(n)| = |A(n)| + |B(n)| = |S(n-1)| + |S(n-2)|$, yang merupakan relasi perulangan Fibonacci. Anda kemudian dapat membuktikan dengan induksi bahwa urutan Anda sama dengan deret Fibonacci.
Kami memiliki dari prinsip pertama bahwa jumlah komposisi menjadi bagian ganjil diberikan
$$[z^N] \sum_{q\ge 1} \left(\frac{z}{1-z^2}\right)^q.$$
Ini menyederhanakan menjadi
$$[z^N] \frac{z/(1-z^2)}{1-z/(1-z^2)} = [z^N] \frac{z}{1-z-z^2}.$$
Sekarang $$F(z) = \frac{z}{1-z-z^2}$$ adalah OGF dari bilangan Fibonacci dan kami memiliki klaimnya.