Generoivista funktioista

Abstract

Tässä tutkielmassa perehdytään generoivien funktioiden menetelmään, missä tarkoituksena on yleensä etsiä eksakti kaava annetulle lukujonolle (a_n), missä n saa arvot nollasta äärettömään. Generoivien funktioiden avulla voidaan myös todistaa kaavojen yhtäpitävyyksiä tai löytää esimerkiksi uusi rekursiivinen tai approksimoitu kaava. Kahdesta lähestymistavasta, muodollisesta ja analyyttisestä, tämän tutkielman lähtökohtana on generoivien funktioiden muodollinen teoria, ja esitellyt generoivat funktiot ovatkin muodollisia potenssisarjoja lukuun ottamatta Dirichlet’n sarjan generoivaa funktiota. Tutkielman tavoitteena on esitellä lukijalle generoivien funktioiden menetelmän perusteet tästä lähtökohdasta, ja antaa välineitä menetelmän käyttöön teorian ja esimerkkien kautta.Aluksi tutkielmassa esitellään lyhyesti muodollisen potenssisarjan määritelmä ja siihen liittyvää teoriaa. Lisäksi käydään läpi tutkielmassa käytettyjä yleisesti tunnettuja kaavoja. Luvussa 3 esitellään generoivien funktioiden metodin pääperiaatteet ja yleisimmät tavallisen generoivan funktion muodot, eli tavallinen potenssisarjamuotoinen generoiva funktio ja eksponentiaalinen generoiva funktio. Edellisten käyttöä demonstroidaan esimerkkien kautta. Luvussa 4 keskitytään edellisessä luvussa esiteltyjen generoivien funktioiden laskuoppiin ja luvussa 5 esitellään vielä yksi edellisistä eroava generoivan funktion muoto, eli Dirichlet’n sarjan generoiva funktio, sekä tämän laskuoppia.Päälähteenä tutkielmassa on käytetty Herbert S. Wilfin kirjaa generatingfunctionology.

Asiasanat: Muodollinen potenssisarja, generoiva funktio, algebrallinen, Taylorin sarja, Dirichlet?n sarja, suurin yhteinen tekijä, aritmeettinen funktio, multiplikatiivinen funktio, Möbiuksen funktio