Relacionet rekurente

Relacion rekurent quajmë ekuacionin që shpreh termin e n-të të një sekuence në funksion të k termave paraardhës, për disa k të fiksuar (të pavarur nga n). Pasi jepen k termat fillestarë të një sekuence, relacioni rekurent lejon llogaritjen në mënyrë rekursive të të gjithë termave të sekuencës.

Kushtet fillestare për një sekuencë të definuar në mënyrë rekursive specifikojnë termat që i paraprijnë termit n ku hyn në fuqi relacioni i rekurencës. Duke përdorur Induksionin Matematik ( një mënyrë vërtetimi në matematikë) mund të tregojmë se një relacion rekurent bashkë me kushtet fillestare të tij përcakton një zgjidhje unike.

Vargu i Fibonaçit (Fibonacci Sequence)

Është emëruar pas matematikanit Italial Leonardo Fibonacci, i cili kishte lindur në shekullin e XII.

Vargu i Fibonaçit është seri e numrave ku secili numër është shuma e dy numrave paraardhës. Për shembull 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610...

Matematikisht e shkruajmë:

$F_n=F_{n-1}+F_{n-2}$ :

Këtë varg ( tash të famshëm ) për herë të parë Fibonaçi e prezantoi si zgjidhje për problemin e lepujve që thotë : Nëse një çift lepujsh i lëmë në një fushë (lepujt mund të riprodhohen pas 1 muaji, çdo lepur femër lindë një lepur mashkull dhe një femër dhe lepujt nuk ngordhin, kushte të pamundura biologjikisht), sa çifte lepujsh do të Kemi pas çdo muaji?

Faktorieli

Faktorieli funksion i rëndësishëm në matematikë (prodhim i të gjithë numrave natyrorë paraardhës të numrit të zgjedhur), gjithashtu mund të shprehet si relacion rekurent me kushte fillestare 0! = 1 dhe 1! = 1 $n!=n(n-1)!$ ose më e kuptueshme nëse e shprehim faktorielin sikur një funksion ($n!=f(n)$) atëherë kemi:

$f(n)=n*f(n-1)$.

Koeficientët binomialë

Një shembull i thjeshtë i një lidhjeje shumëdimensionale të përsëritjes jepet nga koeficientët binomialë $(\genfrac{}{}{0ex}{}{n}{k})$, të cilët numërojnë numrin e mënyrave të zgjedhjes së elementeve nga një grup elementesh.

$(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n-1}{k-1})+(\genfrac{}{}{0ex}{}{n-1}{k}),$

Ato mund të llogariten nga relacioni i përsëritjes me rastet bazë $(\genfrac{}{}{0ex}{}{n}{0})=(\genfrac{}{}{0ex}{}{n}{n})=1$. Përdorimi i kësaj formule për të llogaritur vlerat e të gjithë koeficientëve binomial gjeneron një grup të pafund të quajtur trekëndëshi i Paskalit. Të njëjtat vlera mund të llogariten gjithashtu drejtpërdrejt nga një formulë e ndryshme që nuk është një përsëritje, por përdor faktorialë, shumëzim dhe pjesëtim dhe jo vetëm mbledhje:

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!(n-k)!}.$

Koeficientët binomialë mund të llogariten gjithashtu edhe me një përsëritje njëdimensionale:

$(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n}{k-1})(n-k+1)/k,$

me vlerën fillestare $(\genfrac{}{}{0ex}{}{n}{0})=1$ (Pjestimi nuk shfaqet si thyesë për të theksuar se duhet të llogaritet pas shumëzimit, për të mos futur numra thyesorë). Kjo përsëritje përdoret gjerësisht në kompjuterë sepse nuk kërkon të ndërtohet një tabelë siç bën përsëritja dydimensionale, dhe përfshin numra të plotë shumë të mëdhenj siç bën formula me faktorialë (nëse përdoret $(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n}{n-k}),$të gjithë numrat e plotë të përfshirë janë më të vegjël se rezultati përfundimtar).

Zgjidhja e relacioneve rekurente lineare homogjene

Releacionet rekurente mund të jetë vështirë të zgjidhen, por për relacionet rekurente homogjene mund të përdorim dy ide, e para këto relacione rekurente kanë zgjidhje të formës $a_n=r^n$ ku r është konstante. Ndërsa ideja tjetër është se kombinimi linear i dy zgjidhjeve të relacioneve rekurente homogjene është gjithashtu një zgjidhje.

Teoremë

Le të jenë $c_1$ dhe $c_2$ numra real. Supozojmë se $r^2-c_{1}r-c_2=0$ ka dy rrënjë të ndryshme $r_1$ dhe $r_2$. Atëherë vargu {$a_n$} është zgjidhje e relacionit rekurent $a_n=c_1{a}_{n-1}+c_2{a}_{n-2}$ atëherë dhe vetëm atëherë kur $a_n={\alpha }_1{r}_1^n+{\alpha }_2{r}_2^n$ për n = 0, 1, 2, ..., ku ${\alpha }_1$ dhe ${\alpha }_2$ janë konstante.

Shembull

Problemi: Cila është zgjidhja e relacionit rekurent $a_n=a_{n-1}+2a_{n-2}$ , me kushte fillestare $a_0=2$ dhe $a_1=7$ ?

Zgjidhje: Nga Teorema kemi:

$r^2-r-2=0$ , ku r=2 dhe r= -1.

Pra, vargu {$a_n$} është zgjidhje atëherë dhe vetëm atëherë kur:

$a_n={\alpha }_1{2}^n+{\alpha }_2(-1{)}^n$, për disa konstante ${\alpha }_1$ dhe ${\alpha }_2$.

Prej kushteve fillestare formojmë sistemin:

$a_0=2={\alpha }_1+{\alpha }_2$

$a_1=7={\alpha }_{1}2+{\alpha }_2(-1)$

Që pas zgjidhjes marrim ${\alpha }_1=3$ dhe ${\alpha }_2=-1$.

Kështu që zgjidhja e relacionit rekurent homogjen dhe kushteve fillestare të tij është vargu {$a_n$} i shprehur:

$a_n=3*2^n-(-1{)}^n$

Aplikimet e relacioneve rekurente

Shkenca kompjuterike

Relacionet rekurente kanë rëndësi të madhe në analizim të algoritmeve. Nëse një algoritëm është i dizajnuar që të ndajë një problem në probleme më të vogla, koha që kërkon ai algoritëm për ekzekutim është i shprehur me një relacion rekurent. Një shembull i thjeshtë është algoritmi për të gjetur një element specifik në një bashkësi elementesh, në rastin më të keq. Një algoritëm naiv do të fillojë kërkimin prej anës së majtë në të djathtën, rasti më i keq është kur elementi gjendet në fund, pra numri i hapave është n. Algoritëm më i mirë për këtë punë është algoritmi i kërkimit binarë (aplikohet vetëm në listë të rradhitur), ky algoritëm së pari shikon nëse vlera specifike gjendet në mes të listës, nëse jo, shikon nëse elementi që kërkojmë është më i vogël apo më i madh se elementi i mesit, në këtë pikë gjysma tjetër e listës mund të largohet dhe algoritmi rifillon ekzekutimin në gjysmën e mbetur. Numri i hapave të këtij algoritmi mund të shprehet si relacion rekurent

$c_n=1+\frac{c_n}{2}$ me kusht fillestarë $c_1=1$.