Rekurencat

## Relacionet rekurente 
Në matematikë, një relacion rekurent është një ekuacion që shpreh termin e n-të të një sekuence në funksion të k termave paraardhës, për një k të fiksuar (të pavarura nga n), që quhet **rendi i relacionit**. Pasi jepen k termat fillestarë të një sekuence, relacioni i rekurencës lejon llogaritjen e të gjithë termave të atij vargu.
Shpesh termi rekursiv përdoret si sinonim i fjalës “i llogaritshëm” sepse thuhet se një funksion mund të përcaktohet në mënyrë rekursive vetëm nëse ai mund të llogaritet nga ndonjë progam. Në rastin e përgjithshëm, një relacion rekurrent definohet me:

{\displaystyle a_{n}=f(a_{n-1},a_{n-2},...,a_{0})} 
 
Ku f është një funksion i dhënë.

Relacioni rekurent quhet **linear** nëse termi i *n*-të mund të shprehet si funksion linear i termave paraardhës. Rekurenca lineare është **homogjene** nëse nuk përmban terma që nuk janë shumëfisha të kufizave paraardhëse a_i. 

Kështu, rekurenca lineare homogjene e shkallës *k* ka formën:

{\displaystyle a_n = c_1 a_{n-1}+c_2 a_{n-2}+...+c_k a_{n-k}}

ku {\displaystyle c_1, c_2, ..., c_k} janë numra realë, dhe {\displaystyle  c_k} është i ndryshëm nga zero.
Ndërsa relacioni rekurent quhet **johomogjen** nëse ka formën:

{\displaystyle a_n =c_1 a_{n-1}+c_2 a_{n-2}+...+ c_k a_{n-k}+F(n)} 

ku {\displaystyle c_1, c_2, ... , c_k} janë numra realë dhe {\displaystyle F(n)} është funksion jo-zero i cili varet vetëm nga n.

## Shembuj 
### Vargu i Fibonaçit 
Rekurenca e rendit të dytë e fituar nga numrat e Fibonaçit është shembull i një relacioni rekurent homogjen. Vargu i Fibonaçit është i definuar me ekuacionin 

{\displaystyle F_{n}=F_{n-1}+F_{n-2}, n\geq 2} 

dhe kushtet fillestare

{\displaystyle F_{0}=0} 
alt=Trekëndëshi i Paskalit|parapamje|Trekëndëshi i Paskalit
{\displaystyle F_{1}=1} 

Në mënyrë të qartë, sekuenca jep ekuacionet
alt=Golden Ration- Vargu i Fibonaçit|parapamje|Golden Ration- Vargu i Fibonaçit
{\displaystyle F_{2}=F_{1}+F_{0}}, 

{\displaystyle F_{3}=F_{2}+F_{1}}, 

{\displaystyle F_{4}=F_{3}+F_{2}}, ...

Kështu fitojmë vargun me kufizat fillestare {\displaystyle 0,1,1,2,3,5,8,13,21,34,...} 

Këto kufiza formojnë edhe Relacionin e "Artë" .

Rekurenca mund të zgjidhet me formulën e Binetit, e cila përfshin fuqitë e dy rrënjëve të polinomit karakteristik {\displaystyle t^{2}=t+1}  dhe fitohet ekuacioni:

{\displaystyle F_{n}={\frac {1}{\surd 5}}({\frac {1+\surd 5}{2}})^{n}-{\frac {1}{\surd 5}}({\frac {1-\surd 5}{2}})^{n}} ,

ndërsa funksioni gjenerues i sekuencës është funksioni racional {\displaystyle {\frac {t}{1-t-t^{2}}}} .

### Kullat e Hanoit 
alt=Kullat e Hanoit 1|parapamje|Kullat e Hanoit 1
Kulla e Hanoit është një enigmë popullore e fundit të shekullit të nëntëmbëdhjetë e shpikur nga matematikani francez Édouard Lucas. Kjo enigmë përbëhet nga tre kunja të montuara në një tabelë së bashku me disqe të madhësive të ndryshme. Fillimisht këto disqe vendosen në kunjin e parë sipas madhësisë, me më të madhin në fund. Rregullat e enigmës lejojnë që disqet të zhvendosen një nga një nga një kunj në tjetrin për sa kohë që një disk nuk është kurrë i vendosur mbi një disk më të vogël. Qëllimi i enigmës është që të gjitha disqet të jenë në kunjin e dytësipas madhësisë, me më të madhin në fund.

Le të jetë {\displaystyle H_n} numri i lëvizjeve të nevojshme për të zgjidhur enigmën e Kullës së Hanoit me n disqe. Gjejmë një relacion rekurent për sekuencën {\displaystyle H_n}.

Fillojmë me {\displaystyle n} disqe në kunjën e parë. Ne mund t'i transferojmë {\displaystyle n-1} disqet e sipërme në kunjën e tretë, duke ndjekur rregullat e enigmës, me {\displaystyle H_{n-1}} lëvizje. Diskun më të madh e mbajmë të fiksuar gjatë këtyre lëvizjeve. Pastaj, e përdorim një lëvizje për të transferuar diskun më të madh në kunjin e dytë. Së fundmi, i transferojmë {\displaystyle n-1} disqet tjera nga kunji 3 në kunjin 2 duke përdorur {\displaystyle H_{n-1}} lëvizje përsëri. Kjo tregon se enigmën e Kullave të Hanoit me {\displaystyle n} disqe mund t'a përfundojmë duke përdorur {\displaystyle 2H_{n-1}+1} lëvizje.
alt=Kullat e Hanoit 2|parapamje|Kullat e Hanoit 2
Pra relacioni rekurent i formuar është:

{\displaystyle H_{1}=1} 

{\displaystyle H_{n}=2H_{n-1}+1,n\geq 2} 

me zgjidhjen e tij fitojmë ekuacionin: {\displaystyle H_{n}=2^{n}-1} 

### Vargu aritmetik dhe vargu gjeometrik 
Vargu aritmetik është vargu i formës  {\displaystyle a, a+d, a+2d, ...} , pra, i cili fillon me një term *a* dhe secili term i rradhës fitohet duke ia shtuar termit paraardhës numrin *d*. Kështu vërejmë se vargu aritmetik mund të definohet në mënyre rekurente me
 
{\displaystyle a_1=a}  dhe

{\displaystyle a_{k+1}=a_k+d, k\geq1}
 
Zgjidhja e kësaj rekurence jep ekuacionin:
  
{\displaystyle a_n=a+(n-1)d} 

Ndërsa vargu gjeometrik i cili ka formën {\displaystyle a, ar, ar^2, ar^3, ...}  mund të definohet në formë rekursive si:
  
{\displaystyle a_1=a}  dhe
  
{\displaystyle a_{k+1}=ra_k, k\geq1} 

Zgjidhja e të cilit do të ishte: {\displaystyle a_{n+1}=ar^n} 

### Koeficientët binomialë 
Koeficientët binomialë \tbinom{n}{k} , të cilët numërojnë në sa mënyra mund të zgjedhen *k* elemente nga bashkësia me *n* elemente janë shembull i relacioneve rekurente shumëdimensionale. Për t'i shprehur këta koeficientë në formë rekursive përdoret Identiteti i Paskalit

\binom{n}{k} = \binom{n-1}{k}+\binom{n-1}{k-1} 

me kushtet fillestare:

\binom{n}{0} = \binom{n}{n} =1

Me këto formula gjenerohet vargu i pafundëm i njohur si Trekëndëshi i Paskalit. Këta terma gjenden edhe me formulën:

\binom{n}{k}  = \frac{n!}{k!(n-k)!}

## Zgjidhja e relacioneve rekurente homogjene 
Jo të gjitha relacionet rekurente mund të zgjidhen, por në vijim po shqyrtojmë rastet që mund të zgjidhen me metodën e zevendësimit dhe metodën e koeficientëve konstantë - ekuacionit karakteristik.

### Zgjidhja me metodën e zëvendësimit 
Metoda më e thjeshtë e zgjidhjes së relacioneve rekurente është metoda e zëvendësimit. Fillimihst e zëvendësojmë vlerën e {\displaystyle a_{n-1}} në ekuacionin e dhënë, pastaj vlerën e {\displaystyle a_{n-2}}, {\displaystyle a_{n-3}}, etj. Dhe kështu, tek relacionet rekurente të rendit të parë do të mund të vërejmë një ekuacion i cili më pas duhet të vërtetohet, p.sh. me anë të iduksionit matematik.

Kjo metodë funksionon mirë vetëm për relacionet e rendit të parë, dhe për disa relacione të rendit të dytë.

### Zgjidhja me anë të ekuacionit karakteristik kur rrënjët janë të ndryshme 
Le të jenë c_1, c_2,..., c_k numra realë. Supozojmë se ekuacioni karakteristik 

{\displaystyle r^k - c_1 r^{k-1} = ... - c^k = 0}

ka k rrenje {\displaystyle r_1, r_2, ... , r_k}. Atëherë vargu \{a_n\} është zgjidhje e relacionit rekurent

{\displaystyle a_n = c_1 a_{n-1} + c_2 a_{n-2} + ... + c_k a_{n-k}}

atëherë dhe vetëm atëherë kur 

{\displaystyle a_n = \alpha_1 r_1^n + \alpha_2 r_2^n + ... + \alpha_k r_k^n}

për n=1,2,...   ku \alpha_1, \alpha_2, ..., \alpha_k janë konstante.

### Zgjidhja me anë të ekuacionit karakteristik kur rrënjët mund të mos jenë të gjitha të ndryshme 
Le të jenë {\displaystyle c_1, c_2, c_3,..., c_k} numra realë. Supozoni se ekuacioni karakteristik

{\displaystyle r^k-c_1r^{k-1}-...-c_k=0}

ka {\displaystyle t} rrënjë të ndryshme {\displaystyle r_1, r_2, ..., r_t} me shumëfisha {\displaystyle m_1, m_2, ..., m_t}, përkatësisht, pra që {\displaystyle m_1 \geq 1} për {\displaystyle i=1, 2, ..., t} dhe {\displaystyle m_1+m_2+...+m_t=k}.  Atëherë një varg \{a_n\} është një zgjidhje e relacionit rekurent

{\displaystyle a_n=c_1a_{n-1}+c_2a_{n-2}+...+c_ka_{n-k}}

nëse dhe vetëm nëse

{\displaystyle a_n=(\alpha_{1,0}+\alpha_{1,1}n+...+\alpha_{1,m_1-1}n^{m_1-1})r_1^n}

{\displaystyle +(\alpha_{2,0}+\alpha_{2,1}n+...+\alpha_{2,m_2-1}n^{m_2-1})r_2^n}

{\displaystyle +...+(\alpha_{t,0}+\alpha_{t,1}n+...+\alpha_{t,m_t-1}n^{m_t-1})r_t^n}

për {\displaystyle n=0,1,2,...,} ku {\displaystyle \alpha_{i,j}} janë konstante për {\displaystyle 1\leq i\leq t} dhe {\displaystyle 1\leq j \leq m_i-1}.

## Zgjidhja e relacioneve rekurente johomogjene 
Rikujtojmë se relacioni rekurent johomogjen kishte formën:

{\displaystyle a_n =c_1 a_{n-1}+c_2 a_{n-2}+...+ c_k a_{n-k}+F(n)}

ku {\displaystyle c_1, c_2, ... , c_k} janë numra realë dhe {\displaystyle F(n)} është funksion jo-zero i cili varet vetëm nga n.

Shënojmë {\displaystyle a_n^{(h)} =c_1 a_{n-1}+c_2 a_{n-2}+...+ c_k a_{n-k}} **pjesën homogjene** të relacionit dhe {\displaystyle a_n^{(p)} =F(n)} **pjesën partikulare**. Atëherë çdo zgjidhje e rekurencës do të jetë e formës {\displaystyle a_n^{(h)}+a_n^{(p)}}.

Nëse {\displaystyle F(n)} mund t'a shënojmë në formën:

{\displaystyle F(n)=(b_tn^t+b_{t-1}n^{n-1}+...+b_1n+b_0)s^n}

ku {\displaystyle b_0, b_1,...,b_n, s} janë numra realë dallojmë dy raste: 

* Nëse {\displaystyle s} nuk është zgjidhje e ekuacionit karakteristik të pjesës homogjene atëherë një zgjidhje partikulare merret:

{\displaystyle a_n^{(p)}=(p_tn^t+p_{t-1}n^{t-1}+...+p_1t+p_0)s^n}.

* Nëse {\displaystyle s} është zgjidhje e {\displaystyle m}-fishtë e ekuacionit karakteristik të pjesës homogjene, atëherë një zgjidhje partikulare merret:

{\displaystyle n^ma_n^{(p)}=(p_tn^t+p_{t-1}n^{t-1}+...+p_1t+p_0)s^n}.

## Aplikimi 
### Biologji 
alt=Shtimi i popullatës së lepujve sipas vargut të Fibonaçit|parapamje|Shtimi i popullatës së lepujve sipas vargut të Fibonaçit
alt=Algoritmi i kërkimit binar|parapamje|Algoritmi i kërkimit binar
Disa nga relacionet më të njohura të rekuerencës e kanë origjinën në përpjekjet për të modeluar dinamikën erritjes së  popullsisë. Për shembull, numrat e Fibonaçit dikur u përdorën si model për rritjen e një popullate lepujsh.Madje, relacionet rekurente shpesh përdoren për të modeluar ndërveprimin e dy ose më shumë popullatave. Për shembull, modeli Nicholson-Bailey për një ndërveprim organizëm-parazit jepet nga

{\displaystyle N_{t+1}=\lambda N_{t}e^{-aP_{t}}} 

{\displaystyle P_{t+1}=N+t(1-e^{-1P_{t}})} 

ku {\displaystyle N_{t}}  përfaqëson organizmat e infektuar, dhe {\displaystyle P_{t}}  parazitët, në kohën {\displaystyle t} .

### Shkenca kompjuterike 
Relacionet rekurente janë gjithashtu të një rëndësie themelore në analizën e algoritmeve. Nëse një algoritëm është projektuar në mënyrë që të ndajë një problem në nënprobleme më të vogla (përçaj dhe sundo), koha e ekzekutimit të tij përshkruhet nga një relacion rekurent.

Një shembull i thjeshtë është koha që i duhet një algoritmi për të gjetur një element në një varg të renditur me  {\displaystyle n}  elementë, në rastin më të keq.

Një algoritëm naiv do të kërkojë nga e majta në të djathtë, një element në të njëjtën kohë. Skenari më i keq i mundshëm është kur elementi i kërkuar është i fundit, kështu që numri i krahasimeve është {\displaystyle n} .

Një algoritëm më i mirë është algoritmi i kërkimit binar. Megjithatë, ai kërkon një varg të renditur. Së pari do të kontrollojë nëse elementi është në mes të vargut. Nëse jo, atëherë do të kontrollojë nëse elementi i mesëm është më i madh apo më i vogël se elementi i kërkuar. Në këtë pikë, gjysma e vargut mund të hidhet poshtë dhe algoritmi mund të ekzekutohet përsëri në gjysmën tjetër. Numri i krahasimeve do të jepet nga relacioni rekurent

{\displaystyle c_{1}=1} 

{\displaystyle c_{n}=1+c_{n/2},n\geq 2}
 
kompleksiteti kohor i të cilit do të jetë {\displaystyle O(log_{2}(n))} .

__FORCETOC__
__INDEX__