Rekursioyhtälöitä

Rekursioyhtälö on matemaattinen yhtälö, jossa ratkaistava termi esiintyy myös yhtälön toisella puolella, mutta pienemmällä indeksillä. Se määrittelee jonon tai funktion termien arvon suhteessa sen edellisiin termeihin. Yksinkertaisin rekursioyhtälö on ensimmäisen kertaluvun lineaarinen rekursioyhtälö, joka voidaan esittää muodossa $a_n = c a_{n-1} + d$, missä $a_n$ on jonon $n$:s termi, $c$ ja $d$ ovat vakioita, ja $n-1$ on edellinen termi.

Rekursioyhtälöiden ratkaiseminen tarkoittaa yleensä suljetun muodon löytämistä, joka ilmaisee jonon tai funktion termin suoraan indeksin $n$ funktiona ilman edellisiä termejä. Tämä on hyödyllistä, koska se mahdollistaa jonon tai funktion arvojen laskemisen nopeasti mille tahansa indeksille. Erilaisia menetelmiä, kuten karakteristisen yhtälön käyttöä tai generointifunktioita, käytetään rekursioyhtälöiden ratkaisemiseen.

Rekursioyhtälöillä on monia sovelluksia esimerkiksi tietojenkäsittelytieteessä, kombinatoriikassa ja taloustieteessä. Niitä käytetään kuvaamaan esimerkiksi fibonaccin lukujonoa, algoritmien aikakompleksisuutta ja populaatiodynamiikkaa. Yksinkertainen esimerkki rekursioyhtälöstä on fibonaccin lukujono, jonka määritelmä on $F_n = F_{n-1} + F_{n-2}$ alkuarvoilla $F_0 = 0$ ja $F_1 = 1$.