Relasi Rekurensi

Relasi rekurensi mendefinisikan setiap suku dari suatu barisan dalam bentuk suku-suku sebelumnya, dan fungsi pembangkit menyediakan jalur sistematis menuju solusi bentuk tertutup.

Definition

Relasi rekurensi adalah persamaan yang menyatakan setiap suku dari suatu barisan sebagai fungsi dari satu atau lebih suku sebelumnya bersama dengan kondisi awal yang menentukan barisan tersebut secara unik.

Scope

Topik ini mencakup rekurensi linear dengan koefisien konstan dan solusi persamaan karakteristiknya, rekurensi Fibonacci dan Catalan, rekurensi bagi-dan-taklukkan (divide-and-conquer), serta metode fungsi pembangkit yang mengubah rekurensi menjadi persamaan aljabar. Ini menjembatani penghitungan elementer dan studi analitik tentang laju pertumbuhan.

Core questions

• Bagaimana suatu barisan didefinisikan secara rekursif dari suku-suku sebelumnya dan nilai-nilai awal?
• Bagaimana persamaan karakteristik menyelesaikan rekurensi linear dengan koefisien konstan?
• Bagaimana fungsi pembangkit mengubah rekurensi menjadi persamaan aljabar yang dapat dipecahkan?
• Bagaimana rekurensi bagi-dan-taklukkan menggambarkan waktu berjalan algoritma?

Key concepts

• Rekurensi linear dengan koefisien konstan
• Persamaan karakteristik
• Bilangan Fibonacci
• Bilangan Catalan
• Rekurensi bagi-dan-taklukkan
• Solusi fungsi pembangkit

Key theories

Metode persamaan karakteristik

Rekurensi linear dengan koefisien konstan diselesaikan dengan mencari akar-akar dari polinomial karakteristiknya; solusi umum adalah kombinasi dari suku-suku eksponensial yang ditentukan oleh akar-akar tersebut dan kondisi awal.

Solusi fungsi pembangkit

Mengalikan rekurensi dengan variabel formal dan menjumlahkannya mengubahnya menjadi persamaan aljabar untuk fungsi pembangkit, yang ekspansinya menghasilkan bentuk tertutup untuk barisan, seperti untuk bilangan Catalan dan Fibonacci.

Clinical relevance

Relasi rekurensi menggambarkan waktu berjalan algoritma rekursif, di mana rekurensi bagi-dan-taklukkan dan teorema master memberikan batas kompleksitas, dan mereka memodelkan proses dinamis dan populasi diskrit.

History

Masalah kelinci Fibonacci pada abad ke-13 menghasilkan rekurensi arketipal; de Moivre dan Euler mengembangkan metode fungsi pembangkit dan akar karakteristik yang tetap menjadi teknik solusi standar.

Key figures

• Leonardo of Pisa (Fibonacci)
• Abraham de Moivre
• Eugene Catalan

Seminal works

• stanley2011

Frequently asked questions

Apa itu bilangan Catalan?

Bilangan Catalan menghitung banyak objek kombinatorial – tanda kurung seimbang, triangulasi, pohon biner – dan memenuhi rekurensi kuadrat yang dapat diselesaikan dengan fungsi pembangkit untuk memberikan bentuk binomial tertutup.

Mengapa menggunakan fungsi pembangkit untuk menyelesaikan rekurensi?

Mereka mengubah keluarga tak terbatas dari persamaan rekursif menjadi satu persamaan aljabar tunggal, dari mana ekspresi bentuk tertutup untuk setiap suku dapat diekstraksi sekaligus.