Lineaire recursieve rijen

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