Tag archieven: recursieve rijen

Op welk cijfer eindigt…

Geplaatst op door

Wat is de rest bij deling door 10 van het 2022ste getal in de rij  

    \[3,3^3,3^{3^3},...\]

  • De gegeven rij kan ook gegeven worden door middel van een recursief voorschrift: t_1=3 en t_{n+1}=3^{t_n}.

  • Berekenen we een paar termen van de rij: 3 , 27 , 7625597484987. We zien dat ze zeer snel toenemen in grootte, maar we hebben wel al 2 keer een 7 achteraan. Zou dat een patroon zijn?

  • Elke term is een viervoud plus 3, want t_n=(4 voud -1)^{t_{n-1}} en omdat elke term in de rij oneven is is t_n dus een 4voud min 1, of met anders geformuleerd : een drievoud plus 3.

  • Dan is t_{n+1}=3^{4v+3}=3^3.3^{4v}=27.81^v.
  • Werken we nu modulo 10: t_{n+1}\equiv 7.1^v\equiv 7.
  • Dus elke term van de rij eindigt op 7, dus ook de 2022ste term.

Lineaire recursieve rijen

Geplaatst op door

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

Opgave 9

Geplaatst op door

Definieer a_1=2018 en a_{n+1}=9^{a_n} voor n=1,2,…
Bepaal de laatste twee cijfers van a_{2018}.

Antwoord

  • We kunnen voor k=1,2,...,10 de laatste twee cijfers berekenen van 9^k. We vinden 9^{10}=3486784401 en eindigt dus op 01.
  • Als (9^{10})^n eindigt op 01, dan zal ook (9^{10})^{n+1} eindigen op 01, want (9^{10})^{n+1}=(9^{10})^n.9^{10}=(\cdots 01).(\cdots 01)=(\cdots 01).
  • Door inductie hebben we dus bewezen dat elke macht van 9^ {10} eindigt op 01.
  • Dan is a_2=9^{2018}=(9^{10})^{201}.9^8=(\cdots01).43046721 en dus eindigt a_2 op 21.
  • Verder is a_3=9^{\cdots 21}=(9^{10})^{\cdots 2}.9^1=(\cdots 01).9=\cdots 09. Bijgevolg eindigt a_3 op 09.
  • Nu is a_4=9^{\cdots 09}=(9^{10})^{\cdots 0}.9^9=(\cdots 01).387420489=\cdots 89.
  • Het is duidelijk dat alle verdere termen van de rij  op 89 zullen eindigen.
  • Dus a_{2018} eindigt op 89.