Banyaknya cara untuk merepresentasikan N apapun sebagai jumlah dari bilangan ganjil? [duplikat]

Nov 28 2020

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

9 Magma Nov 28 2020 at 04:05

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.

4 MarkoRiedel Nov 28 2020 at 04:11

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.