Rekurentinės priklausomybės ir rekursinis skaičiavimas

Skaičiuokite trumpo užlipimo būdus pagal paskutinį žingsnį

Pradėję nuo nulinio aukščio, pasiekite trijų vienetų aukštį vieno arba dviejų vienetų žingsniais. Užrašykite jų tvarką. Galimi sąrašai yra (1,1,1), (1,2) ir (2,1): trys rezultatai. Sąrašai (1,2) ir (2,1) atitinka skirtingus tarpinius aukščius, todėl tai skirtingi užlipimo būdai.

Pašalinus paskutinį žingsnį iš užlipimo, kuris baigiasi vienos pakopos žingsniu, lieka užlipimas į dviejų vienetų aukštį. Jei užlipimas baigiasi dviejų pakopų žingsniu, lieka užlipimas į vieno vieneto aukštį. Šie du paskutinio žingsnio atvejai negali sutapti, o kiekvienas užlipimas baigiasi vienu iš šių žingsnių.

Į dviejų vienetų aukštį galima užlipti dviem būdais: (1,1) ir (2), o į vieno vieneto aukštį – vienu būdu: (1). Taigi užlipimo į trijų vienetų aukštį būdų skaičius yra 2+1 = 3. Didesnio uždavinio rezultatus galime suskaičiuoti naudodamiesi mažesnių to paties uždavinio variantų rezultatų skaičiais.

Prieš išvesdami bendrąją formulę, sudarykite trumpą lentelę

Dar kartą peržiūrėkite pamoką „Skaičiavimas, nulis ir natūralieji skaičiai“, kad atskirtumėte baigčių nebuvimą nuo vienos tuščios baigties. Pamoka „Sudėtis ir atimtis“ padeda sujungti nesikertančius atvejus. Remkitės pamoka „Formulės ir paprastų ryšių pertvarkymas“, kad pakeistumėte kintamąjį nurodyta reikšme išlaikydami formulės struktūrą.

Ankstesnėse pamokose apie skaičiavimą taikant sumos ir sandaugos taisykles bei įrodymą indukcijos metodu plėtojami naudingi metodai. Čia reikalingos idėjos paaiškinamos vietoje: sudėkite tik nesikertančių ir visas baigtis apimančių klasių baigčių skaičius, o siūlomą formulę patikrinkite ties pradiniu indeksu ir kiekviename tolesniame žingsnyje. Šiomis dviem idėjomis galite naudotis dar prieš studijuodami bendruosius jų įrodymo metodus.

Skaitydami pirmą kartą, sekite pradinius atvejus laiptų uždavinio ir dvejetainių eilučių lentelėse. Prie uždarųjų formulių grįžkite pasipraktikavę įstatyti reikšmes ir taikyti skirstomumo dėsnį. Paskelbta pamoka „Laipsnių savybės ir laipsninės funkcijos“ parengia darbui su laipsniais geometrinių sekų formulėse; ji nepateikia skaičiavimui reikalingo suskaidymo.

Taisyklei reikia indeksų intervalo ir pradinių reikšmių

Seka yra sutvarkytas reikšmių sąrašas, kurio elementai pažymėti indeksais. Čia indeksai yra neneigiami sveikieji skaičiai: a₀,a₁,a₂,… . Apatinis indeksas nurodo vietą sekoje; jis nėra daugiklis. Nurodžius a₀, o ne a₁, pasikeičia vieta, nuo kurios pradedama.

Rekurentinis sąryšis susieja sekos narį su ankstesniais nariais. Pavyzdžiui, aₙ = aₙ₋₁+3, kai n ≥ 1, leidžia apskaičiuoti kiekvieną kitą narį, kai duota viena pradinė reikšmė a₀. Vien taisyklė sekos neapibrėžia: pradinės reikšmės 2 ir 5 pagal tą pačią taisyklę duoda skirtingas sekas.

Rekurentinio sąryšio eilė yra didžiausias jame naudojamas indekso poslinkis atgal. Taisyklė uₙ = uₙ₋₁+uₙ₋₂, kai n ≥ 2, yra antrosios eilės ir tokia forma reikalauja u₀ ir u₁. Turint šias pradines reikšmes, kiekvienas naujas narys vienareikšmiškai apskaičiuojamas iš jau nustatytų narių. Šis samprotavimas žengiant pirmyn pagrindžia ir egzistavimą, ir vienatinumą nurodytoje srityje.

Netaikykite taisyklės už jos indeksų intervalo ribų. Kai n = 1, antrosios eilės reiškiniui reikėtų u₋₁, kuris nėra apibrėžtas. Pradinės reikšmės nusako atvejus su mažais indeksais, kuriems bendrasis suskaidymas netaikomas.

Įrodykite laiptų uždavinio rekurentinį sąryšį dviem grįžtamais atvejais

Tegul uₙ žymi sutvarkytų sąrašų, sudarytų iš 1 ir 2, kurių suma lygi n, skaičių. Yra vienas tuščias sąrašas, kurio suma lygi nuliui, todėl u₀ = 1. Yra vienas sąrašas, kurio suma lygi vienetui, (1), todėl u₁ = 1.

Kai n ≥ 2, suskaidykite visus sąrašus pagal paskutinį žingsnį. Pašalinus paskutinį 1, jo klasė atvaizduojama į visus sąrašus, kurių suma lygi n−1; pridėjus 1 gale, atkuriamas pradinis sąrašas. Pašalinus paskutinį 2, analogiškai gaunami visi sąrašai, kurių suma lygi n−2, o atvirkštinis veiksmas yra 2 pridėjimas gale.

Vienetu besibaigiančios sekos yra (1,1,1,1),(1,2,1),(2,1,1), gautos iš (1,1,1),(1,2),(2,1). Dvejetu besibaigiančios sekos yra (1,1,2),(2,2), gautos iš (1,1),(2). Taigi u₄ = u₃ + u₂ = 3 + 2 = 5.

Šios atitiktys yra abipusiškai vienareikšmės, klasės nesikerta ir apima visus sąrašus. Todėl uₙ = uₙ₋₁+uₙ₋₂, kai n ≥ 2. Nereikia nei dalybos, nei prielaidos, kad abiejose klasėse yra vienodas sąrašų skaičius.

Lentelė prasideda reikšmėmis 1,1,2,3,5,8,13, atitinkančiomis indeksus nuo 0 iki 6. Penki sąrašai, kurių elementų suma lygi keturiems, pasiskirsto taip: trys baigiasi 1, o du – 2. Baigtinė lentelė patikrina šį pavyzdį; argumentas, grindžiamas apgręžiamomis atvejų konstrukcijomis, įrodo taisyklę kiekvienam n iš nurodyto intervalo.

Ta pati taisyklė gali skaičiuoti skirtingus objektus arba naudoti skirtingus indeksus

Išklokite n vienetinių langelių juostą vieno ir dviejų vienetų ilgio plytelėmis, nepalikdami tarpų ir jų neperdengdami. Skaitydami plytelių ilgius iš kairės į dešinę, gauname būtent sąrašą iš 1 ir 2, kurio elementų suma lygi n. Sudėdami tokio ilgio plyteles, atliekame atvirkštinę konstrukciją. Taigi šių juostos išklojimų skaičius taip pat yra uₙ, įskaitant vieną nulinio ilgio juostos išklojimą.

Naudokime Fibonačio sekos susitarimą: F₀ = 0, F₁ = 1 ir Fₙ = Fₙ₋₁+Fₙ₋₂, kai n ≥ 2. Pagal jį gauname 0,1,1,2,3,5,8,… . O mūsų lipimo būdų skaičiai prasideda 1,1,2,3,5,8,… . Pagal šį susitarimą uₙ = Fₙ₊₁, o ne Fₙ.

Šis poslinkis galioja, kai n = 0 ir n = 1, o toliau abi pusės tenkina tą patį rekurentinį sąryšį. Žinomas sekos pavadinimas niekada nepakeičia nurodytų pradinių reikšmių ir pradinio indekso. Skirtingus objektus gali sieti tas pats rekurentinis sąryšis, nors jie nėra tapatūs rezultatai.

Paskutinis 1 reikalauja prieš jį esančio 0

Tegu bₙ žymi n ilgio dvejetainių eilučių, kuriose nėra gretimų 1, skaičių. Eilutę sudaro pažymėtos pozicijos, kuriose įrašyta 0 arba 1. Tuščioji eilutė, žymima ε, yra vienas rezultatas, todėl b₀ = 1. Abi vieno ilgio eilutės leidžiamos, todėl b₁ = 2.

Kai n ≥ 2, leistina eilutė baigiasi arba 0, arba 1. Pirmuoju atveju pašalinkite paskutinį 0; kiekvieną leistiną (n−1) ilgio eilutę galima pratęsti pridedant 0. Antruoju atveju prieš paskutinį skaitmenį turi būti 0, todėl pašalinkite galinį 01; kiekvieną leistiną (n−2) ilgio eilutę galima pratęsti pridedant 01.

Pridėjus galūnę 0, gaunama 000,010,100 iš 00,01,10. Pridėjus galūnę 01, gaunama 001,101 iš 0,1. Šie du atvejai nesikerta ir apima visas penkias eilutes: b₃ = b₂ + b₁ = 3 + 2 = 5.

Abi konstrukcijos turi atvirkštinius pašalinimo atvaizdžius, išlaiko apribojimą ties naująja sandūra ir apibrėžia nesikertančius, visus galimus variantus apimančius atvejus. Todėl bₙ = bₙ₋₁+bₙ₋₂, kai n ≥ 2. Skaičiai prasideda 1,2,3,5,8,13,21, taigi pagal mūsų susitarimą bₙ = Fₙ₊₂.

Kai ilgis lygus trims, eilutės, kurios baigiasi 0, yra 000,010,100; eilutės, kurios baigiasi 01, yra 001,101. Vien pasakyti „pridėkite 1 prie bet kurios leistinos trumpesnės eilutės“ yra klaidinga: pridėjus 1 prie eilutės, kuri jau baigiasi 1, susidaro draudžiamas 11.

Tuščia konstrukcija yra vienas užbaigtas rezultatas

Tuščias lipimas ir tuščioji eilutė duoda po vieną pradinį rezultatą, nes nebelieka nieko pasirinkti. Jų elementų skaičius lygus nuliui, tačiau jų rezultatų aibėje yra vienas elementas. O kai reikalaujama teigiamo ilgio eilutės iš tuščios abėcėlės, nėra nė vieno rezultato.

Mūsų laiptų uždavinio būdų skaičius apibrėžtas tik tada, kai n ≥ 0. Kai kuriose išplėstinėse formulėse neigiamą dydį atitinkantis būdų skaičius laikomas lygiu nuliui, kad būtų paprasčiau užrašyti, tačiau tai yra papildomas susitarimas. Mes naudojame du tiesiogiai nustatomus pradinius atvejus ir laiptų uždavinio rekurentinę formulę taikome tik tada, kai n ≥ 2.

Uždavinyje su kitokiais apribojimais mažų reikšmių atvejai gali skirtis. Jei vieno vieneto dydžio žingsniai draudžiami, pasiekti bendrą dydį, lygų vienetui, neįmanoma. Pakeitus šią taisyklę ir palikus u₁ = 1, būtų įskaičiuotas rezultatas, kurio naujasis uždavinys neleidžia.

Pirmosios eilės aritmetinių ir geometrinių taisyklių išskleidimas

Tarkime, kad A ir d yra realiosios konstantos, a₀ = A, o aₙ = aₙ₋₁+d, kai sveikasis skaičius n ≥ 1. Kol pasiekiamas indeksas n, d pridedamas lygiai n kartų, todėl aₙ = A+nd. Ši aritmetinės progresijos formulė tinka ir tada, kai d yra neigiamas arba lygus nuliui.

Tarkime, kad A ir q yra realiosios konstantos, a₀ = A, o aₙ = q aₙ₋₁, kai n ≥ 1. Jei q ≠ 0, kartotinai daugindami gauname aₙ = A qⁿ, kai n ≥ 0. Kai q neigiamas, narių ženklai gali kaitaliotis; dėl to seka netampa neapibrėžta.

Šalia esančioje lentelėje pateikiami visi šeši nariai ir abu skaičiavimai. Neigiami nariai lieka žemiau nulio linijos. Skirtumai, santykiai ir reikšmės nustatymo iš naujo elgsena priklauso nuo kiekviename skydelyje nurodytos taisyklės, o ne vien nuo grafiko nuolydžio.

Jei q = 0, atskirai palikime a₀ = A ir naudokime aₙ = 0, kai n ≥ 1. Jokios 0⁰ reikšmės nereikia. Jei q = 1, seka yra pastovi ir lygi A. Nustatyti q iš santykio aₙ/aₙ₋₁ galima tik tada, kai šis vardiklis nelygus nuliui.

Sekos grafike pateikiamos reikšmės ties sveikaisiais indeksais. Taškų sujungimas gali palengvinti vaizdo suvokimą, tačiau neapibrėžia narių tarp šių indeksų. Todėl mūsų grafikuose žymimi tik sekos taškai, naudojamos sužymėtos tiesinės skalės, o kai nariai neigiami, matoma nulio lygio linija.

Pastovus papildomas narys sukuria baigtinę geometrinės progresijos sumą

Nagrinėkime a₀ = A ir aₙ = q aₙ₋₁+b, kai n ≥ 1, o A, q ir b yra realiosios konstantos. Dėl papildomo b ši rekurentinė formulė yra nehomogeninė, kai b ≠ 0: pagal taisyklę pridedamas dydis, kuris negaunamas dauginant ankstesnes sekos reikšmes.

Išskleidę gauname a₁ = qA+b, a₂ = q²A+qb+b ir a₃ = q³A+q²b+qb+b. Kai n ≥ 1, bendroji išraiška yra aₙ = qⁿA+b(1+q+…+qⁿ⁻¹). Kiekvienas pridėtas b dauginamas po vieną kartą kiekviename vėlesniame žingsnyje.

Jei q ≠ 1, padauginę baigtinę sumą S = 1+q+…+qⁿ⁻¹ iš q ir atėmę S, gauname (q−1)S = qⁿ−1. Taigi aₙ = qⁿA+b(qⁿ−1)/(q−1). Kai q = 0 ir n ≥ 1, ši išraiška tiesiogiai supaprastėja iki aₙ = b; a₀ = A palikime atskirai.

Jei q = 1, pateikto dalmens vardiklis lygus nuliui, todėl jo naudoti negalima. Pagal pradinę taisyklę kiekviename žingsnyje pridedamas b, todėl aₙ = A+nb. Kai n = 0, visais atvejais naudojama nurodyta pradinė reikšmė; išskleistoje sumoje nėra jokių dėmenų.

Pridėti n nėra tas pats, kas pridėti konstantą

Kai a₀ = A ir aₙ = aₙ₋₁+n, kai n ≥ 1, išskleidžiant rekurentinį sąryšį pridedama 1, tada 2, tada 3 ir taip toliau. Todėl aₙ = A+(1+2+…+n).

Tarkime, S = 1+2+…+n. Po šia suma užrašykite tą pačią sumą atvirkštine tvarka; kiekvienos iš n vienas po kitu užrašytų narių porų suma lygi n+1. Taigi 2S = n(n+1), todėl aₙ = A+n(n+1)/2. Kai n = 0, tuščioji suma lygi nuliui, o formulė duoda A.

Tai paprastas nehomogeninis rekurentinis sąryšis su nuo indekso priklausančiu papildomu dėmeniu. Jo kintantys prieaugiai nėra pastovus aritmetinės progresijos skirtumas. Prieš taikydami geometrinės ar aritmetinės progresijos formulę, patikrinkite, kas iš tikrųjų pridedama pagal rekurentinį sąryšį.

Spėta formulė įrodoma, kai tenkina abi sąlygas

Numanoma uždaro pavidalo formulė turi atitikti visas reikiamas pradines reikšmes ir tenkinti rekurentinį sąryšį kiekvienam jo taikymo srities indeksui. Patikrinti penkias pateiktas reikšmes naudinga ieškant klaidų, tačiau taip negalima įrodyti begalinės sekos formulės.

Kai a₀ = 2 ir aₙ = 2aₙ₋₁+1, numanoma formulė aₙ = 3·2ⁿ−1 duoda 2, kai n = 0. Jei jos reiškinys teisingas indeksui n−1, kita reikšmė yra 2(3·2ⁿ⁻¹−1)+1 = 3·2ⁿ−1. Taigi teisingumas perkeliamas į kitą indeksą.

Kai n = 0, 3·2⁰−1 = 2. Jei aₙ₋₁ = 3·2ⁿ⁻¹−1, tai 2aₙ₋₁+1 = 3·2ⁿ−1. Rodomi nariai 2,5,11,23,47 iliustruoja šią patikrintą taisyklę.

Pradėkite nuo patikrintos pradinės reikšmės ir kartokite šią implikaciją, kol pasieksite bet kurį baigtinį norimą indeksą. Tai vietinis indukcinis argumentas: nėra pirmojo vėlesnio indekso, kuriam formulė galėtų būti klaidinga. Jei taisyklė antrosios eilės, patikrinkite abi pradines reikšmes ir žengdami į priekį naudokite abu ankstesnių narių reiškinius.

Bet kuri pateikta baigtinė pradinių narių atkarpa gali būti ir kitos sekos pradžia. Pavyzdžiui, aₙ = n ir cₙ = n+n(n−1)(n−2)(n−3) sutampa, kai n = 0,1,2,3, o kai n = 4, skiriasi. Vien spėtas dėsningumas neužtikrina, kad rekurentinis sąryšis galios netikrintiems indeksams.

Ne kiekvienas sąryšis nustato kitą reikšmę

Kai aₙ = q aₙ₋₁+b, norint atkurti ankstesnę reikšmę pagal aₙ₋₁ = (aₙ−b)/q, būtina, kad q ≠ 0. Kai q = 0, kiekviena pradinė reikšmė duoda tą pačią kitą reikšmę b, todėl žinant, kad a₁ = b, neįmanoma atkurti a₀.

Toks sąryšis kaip aₙ² = aₙ₋₁ nebūtinai vienareikšmiškai nustato kitą reikšmę realiųjų skaičių aibėje. Pradėjus nuo a₀ = 4, pirmasis sąryšis leidžia a₁ = 2 arba −2; ženklą parenkanti taisyklė būtų papildoma informacija.

Sąryšis aₙ = aₙ+1 yra prieštaringas. Sąryšis aₙ = aₙ nenustato jokio apribojimo. Tai nėra naudingi rekursiniai apibrėžimai, leidžiantys skaičiuoti tolesnes reikšmes. Patikrinkite, ar kiekviena reikalinga tolesnė reikšmė egzistuoja ir yra vienintelė, ir ar rekursinės priklausomybės iš tiesų veda prie žinomų pradinių duomenų.

Pakartotinai naudokite apskaičiuotą dalinį uždavinį, nesujungdami jo variantų

Tiesiogiai rekursiškai skaičiuojant u₄, reikia u₃ ir u₂. Skaičiuojant u₃, vėl reikia u₂. Abu iškvietimai prašo tos pačios skaitinės reikšmės, todėl u₂ galima išsaugoti vieną kartą ir naudoti pakartotinai. Toks rezultatų saugojimas vadinamas memoizacija.

Tikslų u₄ iškvietimų medį sudaro devyni iškvietimų mazgai, bet tik penki skirtingi indeksai – nuo 0 iki 4. Juo suskaičiuojamos penkios lipimo sekos. Šie trys dydžiai turi skirtingas prasmes; u₅ atveju tai yra 15 iškvietimų, šeši skirtingi indeksai ir aštuonios lipimo sekos.

Norint apskaičiuoti u₄, iškviečiami u₃ ir u₂; u₃ iškviečia u₂ ir u₁; kiekvienas u₂ iškviečia u₁ ir u₀. Yra devyni iškvietimų mazgai, bet tik penki skirtingi indeksai – nuo nulio iki keturių. Abu u₂ iškvietimai grąžina du; penki suskaičiuoti žingsnių sąrašai lieka skirtingais rezultatais.

Pakartotinės u₂ užklausos nereiškia dvigubo skaičiavimo variantų skaičiaus įrodyme. Jį atitinkantys trumpesni sąrašai pratęsiami skirtinguose galutiniuose atvejuose arba su ilgesniais prefiksais, todėl gaunami skirtingi pilni sąrašai. Skaidinys apibrėžia skirtingus skaičiuojamus objektus; iškvietimų medis aprašo, kaip apskaičiuojamas skaičius.

Nuo pradinių reikšmių pildoma lentelė pradedama u₀,u₁, tada joje po vieną kartą išsaugomos u₂,u₃,… reikšmės. Jos reikšmės sutampa su teisingos rekursijos reikšmėmis, nes kiekvienam įrašui taikoma ta pati taisyklė ir naudojamos tos pačios pradinės reikšmės. Įrodžius uždarąją formulę, ji yra dar vienas būdas gauti tas reikšmes; spartesnis skaičiavimas negali ištaisyti neteisingo skaičiavimo modelio.

Išnagrinėti pavyzdžiai

Pabandykite patys

1. Palyginkite seką, kurios u₀ = 1,u₁ = 1, su seka, kurios v₀ = 0,v₁ = 1, kai abiejų sekų kiekvienas narys lygus dviejų ankstesnių narių sumai, kai n ≥ 2. Kokios yra jų narių su indeksu trys reikšmės?

   Rodyti atsakymą ir paaiškinimą

   u₃ = 3, o v₃ = 2.

   Jų narių, kurių indeksas yra du, reikšmės yra 2 ir 1. Sudėję atitinkamus du ankstesnius narius, gauname 3 ir 2. Vien rekurentinis sąryšis sekos vienareikšmiškai nenustato.

2. Kodėl eilutėms be gretimų 1 simbolių galioja b₀ = 1 ir kodėl atvejis, kai eilutė baigiasi 01, nenaudojamas vieno simbolio ilgio eilučių skaičiui apibrėžti?

   Rodyti atsakymą ir paaiškinimą

   Yra viena tuščia eilutė. Vieno simbolio ilgio eilutės turi du tiesioginius variantus: 0 ir 1; pabaigai 01 reikia bent dviejų pozicijų.

   Tuščia eilutė tenkina apribojimą. Rekurentinis sąryšis taikomas nuo n = 2, todėl jam nereikia b₋₁ ir jis nepraleidžia leistinos vieno simbolio eilutės 1.

3. Kai a₀ = 2 ir aₙ = q aₙ₋₁, išvardykite narius, kurių indeksai yra 0,1,2,3, kai q = −1 ir kai q = 0.

   Rodyti atsakymą ir paaiškinimą

   Kai q = −1: 2,−2,2,−2. Kai q = 0: 2,0,0,0.

   Neigiamas daugiklis čia lemia ženklų kaitą. Nulinis daugiklis kiekvieną narį su teigiamu indeksu paverčia nuliu, bet išsaugo nurodytą pradinę reikšmę 2; 0⁰ reikšmės nereikia.

4. Kai a₀ = 7 ir aₙ = q aₙ₋₁−2, raskite a₄, kai q = 1, ir apibūdinkite visus narius su teigiamais indeksais, kai q = 0.

   Rodyti atsakymą ir paaiškinimą

   Jei q = 1, tai a₄ = 7−4·2 = −1. Jei q = 0, tai aₙ = −2 visiems n ≥ 1; a₀ lieka 7.

   Kai q = 1, pagal taisyklę kiekviename žingsnyje pridedama −2 ir išvengiama dalybos iš q−1. Kai q = 0, pagal taisyklę ankstesnis narys panaikinamas; pradinį narį su nuliniu indeksu nagrinėkite atskirai.

5. Ar lipimų, kuriais iš viso įveikiamos trys pakopos, skaičių galima rasti sudėjus lipimų, kurie „baigiasi 1“, ir lipimų, kuriuose „yra 1“, skaičius? Paaiškinkite pateikdami vieną sąrašą.

   Rodyti atsakymą ir paaiškinimą

   Ne. Šios grupės persidengia: (1,1,1) priklauso abiem.

   Visuose trijuose būduose užlipti tris pakopas yra 1, o du iš jų baigiasi 1. Sudėjus 3+2, persidengiantys variantai būtų suskaičiuoti du kartus. Suskirstymas į variantus, kurie baigiasi 1, ir variantus, kurie baigiasi 2, yra tinkamas skaidymas į nesikertančias aibes.

6. Ar cₙ = 2ⁿ−1 tenkina a₀ = 2, aₙ = 2aₙ₋₁+1, kai n ≥ 1?

   Rodyti atsakymą ir paaiškinimą

   Ne. Ši formulė tenkina rekurentinį sąryšį, bet pagal ją c₀ = 0, o ne reikalaujama reikšmė 2.

   Teisinga formulė yra 3·2ⁿ−1. Formulė, kuri tenkina skaičiavimo pirmyn lygtį, bet netenkina pradinės reikšmės sąlygos, aprašo kitą seką.

7. Jei aₙ = 0·aₙ₋₁+3, kai n ≥ 1, ir a₁ = 3, ar galima atkurti a₀?

   Rodyti atsakymą ir paaiškinimą

   Ne. Bet kuri realioji pradinė reikšmė a₀ duoda a₁ = 3.

   Pateikus pradinę reikšmę, skaičiavimo pirmyn taisyklė vienareikšmiškai nustato tolesnes reikšmes, tačiau dauginant iš nulio prarandama informacija. Dalyba iš q = 0 nėra leistinas skaičiavimo atgal žingsnis.

8. Paprastai rekursiškai skaičiuojant u₅ pagal du ankstesnius narius, atliekama 15 iškvietimų ir naudojami šeši skirtingi indeksai. Kiek lipimo variantų taip suskaičiuojama ir kas pasikeičia, jei kiekvieno dalinio uždavinio rezultatas išsaugomas vieną kartą?

   Rodyti atsakymą ir paaiškinimą

   Suskaičiuojama 8 lipimo variantų. Išsaugant reikšmes išvengiama pakartotinių skaičiavimų, tačiau 8 variantų skaičius nesumažėja.

   Variantų skaičius yra u₅ = u₄+u₃ = 5+3. Iškvietimai yra užklausos atlikti skaičiavimus, o variantai – žingsnių sekos. Pakartotinai naudojant skaičių, skaičiavimui naudojamas suskaidymas išlieka nepakitęs.

Ką verta įsidėmėti

• Nurodykite indekso reikšmių sritį, rekurentinio sąryšio galiojimo ribas ir būtinas pradines reikšmes; pavyzdžių sąrašas nepateikia bendrosios taisyklės.
• Rekursinį variantų skaičiavimą pagrįskite nesikertančiais, visus variantus apimančiais atvejais ir atvirkštinėmis mažesnių variantų konstravimo procedūromis.
• Viena tuščia baigtis ir nė vienos baigties nėra tas pats; Fibonačio sekos indeksų poslinkiai priklauso nuo nurodytų pradinių reikšmių.
• Išskleidžiant gaunamos paprastos formulės, prireikus atskirai nagrinėjant atvejus q = 0 ir q = 1.
• Patikrinkite kiekvieną pradinę reikšmę ir tolesnių narių apskaičiavimo taisyklę, kad įrodytumėte siūlomą sekos formulę.
• Pakartotiniai iškvietimai, skirtingi atmintyje saugomi daliniai uždaviniai ir skaičiuojamos baigtys yra skirtingi dydžiai.