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

Meetkundige rij en reeks

Een meetkundige rij (MR) u_n  is een rij van een getallen zodat het quotiënt van twee opeenvolgende termen van die rij constant is. Deze constante noemt men de reden
(ratio) r van de rij

  • De algemene term van de rij is : u_n=u_1.r^n
  • Een recursie voorschrift : u_n=u_{n-1}.r
  • De som van n termen van een MR wordt gegeven door

        \[S_n=u_1.\dfrac{1-r^n}{1-r}\]

  • Een meetkundige reeks \sum_{i=1}^{\infty}u_i convergeert als |r|<1. In dat geval is de som van de reeks gelijk aan

        \[S=\dfrac{u_1 }{1-r}\]

Stelling van Dirichlet voor rekenkundige rijen

De Stelling van Dirichlet over rekenkundige rijen, ook bekend onder de naam Priemgetallenstelling van Dirichlet (Duits wiskundige, 1805-1859), is een stelling uit de getaltheorie die handelt over het voorkomen van priemgetallen in rekenkundige rijen.

De stelling luidt dat, als a en b onderling ondeelbaar zijn, dus hun grootste gemene deler gelijk is aan 1, de rij

{\displaystyle a,\ a+b,\ a+2b,\ a+3b,\ a+4b,\ \dots }

oneindig veel priemgetallen bevat. 

De stelling is een veralgemening van een bewering door Euler dat elke rekenkundige rij die met 1 begint oneindig veel priemgetallen bevat. De huidige vorm werd geformuleerd door Legendre en in 1837 bewezen door Johann Dirichlet.

De wiskundewereld heeft zich eigenlijk altijd al beziggehouden met het zoeken naar formules van rijen die oneindig veel priemgetallen bevatten.

De stelling van Erdös en Szekeres

Gegeven is een rij van n^2+1 verschillende getallen. Hieruit kan je zeker ofwel een momotoon dalende ofwel een monotoon stijgende deelrij van n+1 elementen kiezen.

erdos

 

 

szekeres

 

 

 

 

 

 

 

Bekijken we een eenvoudig voorbeeld met n=3. We hebben dus een rij van 10 verschillende getallen en we moeten een monotoon dalende of monotoon stijgende deelrij vinden van 4 elementen.  In 2,6,13,4,8,7,3,50,25,10 zit de deelrij 2,6,8,50 die monotoon stijgend is. Met een rij van 9 elementen lukt het niet om een monotoon dalende of monotoon stijgende deelrij te vinden van 4 elementen. Neem bijvoorbeeld 7,8,9,4,5,6,1,2,3.

Als we de positie van een element in de rij als x-coördinaat en het element van de rij als y-coördinaat gebruiken kunnen we aan de stelling een meetkundige interpretatie geven: zo er is bijvoorbeeld een pad met 4 stijgende verbindingslijnen te vinden bij 17 gegeven punten:

kerstboom018