Lineaire recursieve rijen | Wiskunde is leuk

Een rij $a_n$ voldoet aan een lineaire recurrentie als

$c_ka_{n+k}+c_{k-1}a_{n-k-1}+\cdots+c_1a_{n+1}+c_0a_n=0$

De rij $a_n$ noemt men dan een lineaire recursieve rij.
De karakteristieke veelterm van bovenstaande lineaire recurrentie is de veelterm

$f(x)=c_kx^k+c_{k-1}x^{k-1}+\cdots c_1x+c_0$

Als we $f(x)$ in $\mathbb{C}$ kunnen ontbinden als

$c_k(x-r_1)^{m_1}(x-r_2)^{m_2}\cdotsc_k(x-r_l)^{m_l}$

dan voldoet $a_n$ aan de lineaire recurrentie als en slechts als er functies $g_i(x)$ , met graad kleiner of gelijk aan $m_i-1$ , bestaan zodat

$a_n=g_1(n)r_1^n+\cdots+g_l(n)r_l^n$

Als $m_1=m_2=\cdots=m_l=1$ , dan zijn alle functies $g_i(x)$ constanten.

Enkele speciale gevallen:

Bij een rekenkundige rij is $a_{n+1}=a_n+v$ met $a_0=a$ . Dit is geen lineaire recurrentie. Maar nu is ook $a_{n+2}=a_{n+1}+v$ . Aftrekken van de twee formules geeft : $a_{n+2}-2a_{n+1}+a_n=0$ . Dits is wel een lineaire recurrentie met karakteristieke veelterm $x^2-2x+1=(x-1)^2$ . Bijgevolg is $a_n=(An+B).1^n$ . Het is duidelijk dat $B=a$ , de beginterm van de rij en $A=v$ , het verschil van de rij. Zodoende is het algemeen voorschrift $a_n=n.v+a$ voor $n=0,1,...$
Bij een meetkundige rij is $a_{n+1}=a_n.q$ met $a_0=a$ . Dit is een lineaire recurrentie met karakteristieke veelterm $x-q$ . Bijgevolg is $a_n=A.q^n$ . Uit $a_0=a$ volgt dat $A=a$ en dus is het algemeen voorschrift $a_n=a.q^n$ voor $n=0,1,...$

Voorbeeld : $a_0=1$ en $a_1=4$ en elke ander term is het rekenkundig gemiddelde van de twee vorige termen. Een aantal termen van de rij: $1,4,\frac{5}{2},\frac{13}{4},...$ . Om de algemene term van de rij te bepalen, zoeken we eerst de karakteristieke veelterm van de lineaire recurrentie: $2a_{n+2}-a_{n+1}-a_n=0$ . Dan is $f(x)=2x^2-x-1=2(x-1)(x+\frac{1}{2}$ . Bijgevolg is $a_n=A1^n+B\Big(-\frac{1}{2}\Big)^n=A+B\Big(-\frac{1}{2}\Big)^n$ . Om A en B te bepalen gebruiken we dat $a_0=1$ en $a_1=4$ . Hieruit volgt dat $A=3$ en $B=-2$ , zodat $a_n=3-2\Big(-\frac{1}{2}\Big)^n$