OPOMBA
Zapiski teh predavanj so nekoliko zgoščeni. Pomagate si lahko tudi z razlago v [4].

Oglejmo si dobro znani zgled zaporedja števil $F_0,F_1,F_2,...$, ki je definirano rekurzivno s predpisom

tako definirano zaporedje imenujemo Fibonaccijevo zaporedje, število $F_n$ pa $n$-to Fibonaccijevo število. Tip vprašanja, s kateim se bomo ukvarjali v tem razdelku, je, kako izračunati $n$-to Fibonaccijevo število, ne da bi pred tem izračunali vsa predhodna Fibonaccijeva števila.
Zgornjo nalogo lahko nekoliko posplošimo. Naj bodo $c_0,...,c_d$ poljubna kompleksna števila in naj bo $f:\mathbb{N}_0 \to \mathbb{C}$ poljubna funkcija. Iščemo zaporedje kompleksnih števil $a_0,a_1,a_2,...$, katerega prvih $d$ členov je enakih v naprej predpisanim vrednostim $b_0,...,b_{d-1} \in \mathbb{C}$,

in ki za vsak $n \in \mathbb{N}_0$ zadošča enakosti

Pri tem bomo predpostavili, da je $c_0,c_d \ne 0$, saj bi sicer lahko s preoštevilčenjem dobili enakost istega tipa, vendar z manj členi na levi strani enakosti. Z deljenjem z vodilnim koeficientom $c_d$ lahko predpostavimo celo, da je $c_d = 1$.
Izrazu (2) rečemo linearna rekurzivna enačba s konstannimi koeficienti, enakostim (1) pa začetni pogoji enačbe (1). Če je funkcija $f(n)$ na desni strani enakosti konstantno enaka nič, pristavimo še besedico homogena. Neznanka v enačbi (2) je simbol $(a_n)_{n \in \mathbb{N}_0}$, ki predstavlja neznano zaporedje, in ne neznano število kot smo vajeni pri običajnih enačbah iz srednješolske matematike.

Naj bo $\mathbb{F}$ poljuben obseg. Preslikavi

rečemo zaporedje s členi v obsegu $\mathbb{F}$. Vrednosti $a(n)$, $n \in \mathbb{N}_0$, rečemo člen zaporedja in ga navadno označimo z $a_n$. Zaporedje $a$ pa navadno označimo s simbolom $(a_n)_{\mathbb{N}_0}$, včasih pa tudi površno s simbolom $(a_1,a_2,a_3,...)$. Množico vseh zaporedij s členi v $\mathbb{F}$ označimo z $\mathbb{F}^{\mathbb{N}_0}$.

• Če množico $\mathbb{F}^{\mathbb{N}_0}$ opremimo z operacijami seštevanja, množenja in množenja s skalarjem po komponentah, dobimo algebrsko strukturo, ki zadošča aksiomom algebre.
• Mi se bomo v nadaljevanju omejili na operaciji seštevanja in množenja s skalarjem, ter tako na množico $\mathbb{F}^{\mathbb{N}_0}$ gledali kot na vektorski prostor.
• Spomnimo se, da za vsak vektorski prostor $V$ nad obsegom $\mathbb{F}$ množico vseh linearnih preslikav iz $V$ v $V$ označimo z $End(V)$. Če množico $End(V)$ opremimo z operacijama seštevanja in množenja s skalarjem po komponentah, dobimo vektorski prostor. Če pa na množici $End(V)$ definiramo še množenje kot komponiranje preslikav, postane vektorski prostor $End(V)$ algebra.

• Nas bo še posebej zanimal element množice $End(V)$, ki mu rečemo preslikava pomika in je definiran s predpisom:

  $$E:\mathbb{F}^{\mathbb{N}_0} \to \mathbb{F}^{\mathbb{N}_0}, E(a_0,a_1,a_2,...) =(a_1,a_2,a_3,...).$$

• Naj bo

  $$Q(x) = x^d+c_{d-1}x^{d-1}+...+c_1x+c0, c_0 \ne 0,$$

  polinom s koeficineti v obsegu $\mathbb{F}$. Če namesto nedoločenke $x$ vstavimo preslikavo $E$, dobimo nov element algebre $End(\mathbb{F}^{\mathbb{N}_0})$. Oglejmo si, kdaj je neko zaporedje $(a_n)_{n \in \mathbb{N}_0}$ v njegovem jedru:

  $$(a_n)_{n \in \mathbb{N}_0} \in Ker(Q(E)) \Leftrightarrow ... \Leftrightarrow$$

  $a_{n+d}+c_{d-1}a_{n+d-1}+...+c_1a_{n+1}+c_0a_n = 0$ za vsak $n \in \mathbb{N}_0$. (3)

• Ugotovili smo, da je jedro endomorfizma $Q(E)$ natanko množica vseh rešitev enačbe (3). Polinomu $Q(x)$ pri tem rečemo karakteristični polinom enačbe (3).

Pričnimo z reševanjem homogene enačbe (3). V nadaljevanju bomo predpostavili, da je $\mathbb{F} = \mathbb{C}$. Če želimo enačbo rešiti, moramo poiskati jedro endomorfizma $Q(E)$.

• Karatkeristični polinom $Q(x)$ razcepimo na linearne faktorje.

  $$Q(x) = (x-\lambda_1)^{s_1} \cdots (x - \lambda_k)^{s_k}.$$
• Iz linearne algebre se spomnimo naslednjega izreka.

• Z indukcijo lahko zgornji izrek posplošimo na poljubno število paroma tujih polinomov. Iz tega sledi naslednje:

  $$Ker(Q(E)) = Ker((E- \lambda_1I)^{s_1})\oplus ... \oplus Ker((E-\lambda_kI)^{s_k})$$
• Zadošča torej, da ugotovimo, kaj je jedro $K = Ker((E- \lambda I)^s)$ za poljuben $\lambda \ne 0$ in $s \in \mathbb{N}$. Premislimo najprej, da razsežnost takšnega jedra enaka $s$. V resnici dokažemo nekoliko splošnejšo trditev.

Dokaz

• Zdaj vemo, da je razsežnost jedra $K$ enaka $s$. Zadošča torej najti $s$ linearno neodvisnih zaporedij iz $K$. Z neposrednim računom se prepričamo, da zaporedja

  $$(\lambda^n)_{n \in \mathbb{N}_0},(n \lambda^n)_{n \in \mathbb{N}_0},(n^2\lambda^n)_{n \in \mathbb{N}_0}, ..., (n^{s-1}\lambda^n)_{n \in \mathbb{N}_0}$$

  ležijo v jedru $K$, in ker so očitno linearno neodvisna, tvorijo njegovo bazo. Vsako zaporedje v jedru $K$ je torej neka linearna kombinacija zgornjih zaporedij. Če so $\alpha_0,...,\alpha_{s-1}$ koeficienti takšne linearne kombinacije, ima ustrezno zaporedje obliko $(A(n)\lambda^n)_{n \in \mathbb{N}_0}$, kjer je

  $$A(n) = \lambda_0 + \lambda_1n+...+\lambda_{s-1}n^{s-1}.$$

  S tem smo dokazali:

• Če povzamemo vse dosedaj povedano, ugotovimo, da se splošna rešitev homogene enačbe (3) glasi:

  $$a_n = A_1(n)\lambda^n_1 + A_2(n)\lambda^n_2 +...+A_k(n)\lambda^n_k,$$

  kjer je $A_i(n)$ poljuben polinom stopnje največ $s_i - 1$.

Splošna rešitev nehomogene enačbe

ima obliko

kjer je $b_n$ neka (posebna) rešitev zgornje enačbe in $z_n$ rešitev pripadajoče homogene enačbe

Kadar je funkcija $f(n)$ oblike

kjer je $p(n)$ polinom stopnje $r$ in $\alpha$ $s$-kratna ničla karakterističnega polinoma $Q(x)$ (lahko je tudi $s = 0$), rešitev $b_n$ poiščemo z nastavkom

kjer je $P(n)$ polinom stopnje $r$ z nedoločenimi koeficienti.
Kadar je nehomogeni del $f(n)$ enak vsoti funkcij oblike (*), $f(n) = f_1(n) + f_2(n) + ... + f_k(n)$, je posebna rešitev $b_n$ vsota posebnih rešitev nehomogenih enačb $c_da_{n+d}+c_{d-1}a_{n+d-1}+...+c_0a_n =f_i(n)$, $1 \le i \le k$.

Zgled
Poišči splošno rešitev rekurzivne enačbe

Rešitev