31  Lineaariset rekursiot

31.2 Luku­jonon kaava

Ehkä hieman yllättäen mille tahansa lineaarisesti rekursiiviselle luku­jonolle voidaan löytää kaava. Esitetään menetelmä esimerkin kautta.

Lasketaan hieman ensimmäisiä arvoja, jos säännön­mukaisuus sattuisi löytymään.

Selvää logiikkaa ei löydy, mutta yksi asia on selvä: luku­jono kasvaa hyvin nopeasti. Tarkemmin katsottuna seuraava jäsen on suunnilleen kolmin­kertainen edelliseen nähden, eli kasvu vaikuttaa eksponentiaaliselta.

Tästä motivoituneena tehdään arvaus.

Arvaus 1. Arvataan, että $a_n = c^n$ jollakin vakiolla $c$.

Toimiiko tämä? Jotta pätee $a_{n+2} = 5a_{n+1} - 6a_n$, tulee olla $$c^{n+2} = 5c^{n+1} - 6c^n.$$ Tietysti $c = 0$ toteuttaa yhtälön, mutta tämä ei ole kiinnostavaa. Oletetaan, että $c \neq 0$. Jakamalla puolittain luvulla $c^n$ saadaan $$c^2 = 5c - 6.$$ Tämä on toisen asteen yhtälö, jolla on ratkaisut $c = 2$ ja $c = 3$.

Selvästikään kumpikaan arvauksista $a_n = 2^n$ ja $a_n = 3^n$ ei ole oikein: kummallakaan ei päde $a_1 = 1$. Arvausta pitää parantaa.

Arvaus 2. Arvataan, että $a_n = k \cdot c^n$, missä $k$ on jokin vakio ja $c = 2$ tai $c = 3$.

Huomataan, että tämä toteuttaa edelleen rekursio­yhtälön: yhtälö $$kc^{n+2} = 5kc^{n+1} - 6kc^n$$ selvästi pätee jos $k = 0$, ja jos $k$ ei ole nolla, voidaan jakaa puolittain luvulla $kc^n$ ja saada yhtälö $$c^2 = 5c - 6.$$ Tämä on sama yhtälö kuin aiemminkin, eli $c = 2$ ja $c = 3$ ovat taas ratkaisuja.

Ikävä kyllä tämäkään arvaus ei vielä toimi. Tapauksessa $c = 2$ jonon $a_n = kc^n$ ensimmäiset arvot ovat $a_1 = 2k$ ja $a_2 = 4k$, ja haluamme niiden olevan $a_1 = 1$ ja $a_2 = 5$. Kuitenkaan ei voi saman­aikaisesti päteä sekä $2k = 1$ että $4k = 5$. Vastaavasti tapauksessa $c = 3$ tulisi päteä $3k = 1$ ja $9k = 5$, mikä ei onnistu.

Arvaukseen tarvitaan vielä yksi parannus.

Arvaus 3. Arvataan, että $a_n = x \cdot 2^n + y \cdot 3^n$, missä $x$ ja $y$ ovat joitain vakioita.

Huomataan, että tämäkin arvaus toteuttaa rekursio­yhtälön. Arvauksen 2 kohdalla nimittäin huomattiin, että $$x \cdot 2^{n+2} = 5x \cdot 2^{n+1} - 6x \cdot 2^n$$ ja $$y \cdot 3^{n+2} = 5y \cdot 3^{n+1} - 6y \cdot 3^n.$$ Summaamalla nämä yhtälöt saadaan

Tämä on juuri mitä haluamme: tämä kertoo, että arvauksemme $a_n = x \cdot 2^n + y \cdot 3^n$ toteuttaa yhtälön $$a_{n+2} = 5a_{n+1} - 6a_n.$$

Entä alku­arvot? Jotta pätee $a_1 = 1$, tulee päteä $x \cdot 2^1 + y \cdot 3^1 = 1$ eli $$2x + 3y = 1.$$ Jotta pätee $a_2 = 5$, tulee vastaavasti päteä $x \cdot 2^2 + y \cdot 3^2 = 5$ eli $$4x + 9y = 5.$$ Tämä on yhtälö­pari, jonka ratkaisuksi saadaan $x = -1$, $y = 1$.

Täten $$a_n = 3^n - 2^n$$ toteuttaa rekursio­yhtälön ja alku­arvot menevät oikein, eli tämä antaa oikean tuloksen kaikilla $n$. Lauseke $3^n - 2^n$ on hyvinkin siisti kaava luku­jonolle.

31.3 Esimerkki­tehtäviä

Yksi sovellus­kohde (lineaarisille) rekursioille ovat kombinatoriset ongelmat. Tekstissä Induktiivinen päättely nähtiinkin yksi sovellus liittyen merkki­jonoihin, joissa ei ole kahta $a$-kirjainta peräkkäin.

Tässä annetaan pari algebrallisempaa esimerkkiä.

Vastaus: Ei, lukujen $x$ ja $y$ ei tarvitse olla edes rationaalisia!

Valitaan jokin yksin­kertainen luku­jono, joka on lineaarisesti rekursiivinen. Esimerkiksi $a_n = 2^n$ käy hyvin. Nyt $a_1, a_2, \ldots$ selvästikin toteuttaa lineaarisen rekursio­yhtälön $$a_{n+1} = 2a_n,$$ jota vastaava polynomi­yhtälö on $c-2 = 0$. Tämä luku­jono toteuttaa kuitenkin myös moni­mutkaisempia rekursio­yhtälöitä, kunhan niitä vastaavien polynomien nolla­kohdista löytyy $2$. Esimerkiksi polynomi­yhtälöä $(c-2)(c - \pi) = 0$ vastaa rekursio­yhtälö $$a_{n+2} = (2 + \pi)a_{n+1} - 2\pi a_n,$$ ja luku­jono $a_n = 2^n$ toteuttaa tämänkin yhtälön. Eli yksi vasta­esimerkki tehtävään on $x = 2 + \pi, y = 2\pi$ ja $a_n = 2^n$.

Tässä on taulukoitu vähän useampi Fibonaccin luku.

Tutkitaan aluksi jotakin helppoa tapausta, kuten $n = 2m$. Tulee osoittaa, että $F_m \mid F_{2m}$. Tapauksissa $m = 6$ ja $m = 7$ huomataan, että $$\frac{F_{12}}{F_6} = \frac{144}{8} = 18 = 5 + 13$$ ja $$\frac{F_{14}}{F_7} = \frac{377}{13} = 29 = 8 + 21,$$ mikä vihjaa siihen, että $$F_{2m} = F_m(F_{m-1} + F_{m+1}).$$ (Tämä pätee myös pienemmillä $m$:n arvoilla.)

Miten tällaisen identiteetin voisi todistaa? Yksi suora­viivainen tapa on kirjoittaa $$F_n = \frac{1}{\sqrt{5}}(a^n - b^n),$$ missä $a = (1 + \sqrt{5})/2$ ja $b = (1 - \sqrt{5})/2$ ja sievennellä lausekkeita. Sieventämisessä käytetään apuna tietoja $a^2 = a+1, b^2 = b+1$ ja Vietan kaavoista (Alaluku 12.3.2) (tai suoraan laskemalla) saatavia tietoja $ab = -1, a+b = 1$.

Huomataan, että kahden neliön erotuksena $$\begin{align*} F_{2m} &= \frac{1}{\sqrt{5}}(a^{2m} - b^{2m}) \\ &= \frac{1}{\sqrt{5}}(a^m - b^m)(a^m + b^m) \\ &= F_m(a^m + b^m). \end{align*}$$ Enää riittää perustella, miksi $a^m + b^m = F_{m-1} + F_{m+1}$. Oikeastaan alkuperäistä tehtävää varten riittää perustella vain, että $a^m + b^m$ on kokonais­luku. Tämä on hieman helpompaa, joten teemme vain tämän.

Idea on, että $ab$ ja $a+b$ ovat kokonais­lukuja, ja näistä luvuista voidaan rakentaa muita lausekkeita luvuista $a$ ja $b$. Esimerkiksi yhtälössä $$(a+b)^2 = a^2 + 2ab + b^2$$ termit $(a+b)^2$ ja $2ab$ ovat kokonais­lukuja, joten nyt myös $a^2 + b^2$ on kokonais­luku. Yleisesti voimme todistaa induktiolla, että $a^m + b^m$ on kokonais­luku. Riittää huomata, että summa $a^m + b^m$ saadaan muodostettua lukujen $a+b$ ja $a^{m-1} + b^{m-1}$ tulon kautta: $$(a+b)(a^{m-1} + b^{m-1}) = a^m + b^m + (ab)(a^{m-2} + b^{m-2}).$$ Nyt jos $a^{m-1} + b^{m-1}$ ja $a^{m-2} + b^{m-2}$ ovat kokonais­lukuja, niin myös $a^m + b^m$ on.

Olemme siis todistaneet, että $F_m \mid F_{2m}$. Tehtävän todistamiseksi tarvitaan yleisemmin, että $F_m \mid F_{km}$ kaikilla $k \ge 1$. Tämän todistaminen onnistuu vastaavalla tavalla kuin yllä tapauksessa $k = 2$: tekijöihin­jaolla $x^k - y^k = (x-y)(\cdots)$ saadaan

Sulku­lausekkeen termit voi ryhmitellä pareiksi, joiden summa on muotoa $$(ab)^{mi}(a^{mj} + b^{mj}).$$ Tässä $ab = -1$ on kokonais­luku ja edellä on todistettu, että $a^n + b^n$ on aina kokonais­luku. Väite seuraa.