Cum să rezolvați un raport recursiv

Atunci când căutăm o formulă pentru câteva secvențe matematice, un pas intermediar constă în căutarea unui termen al celei de a unsprezecelea, și nu în funcție de "n", ci ca o secvență a primilor termeni. De exemplu, ar fi frumos să aibă o formulă închisă pentru termenul n-lea a secvenței Fibonacci, dar, uneori, tot ce trebuie este o relație recursiv, adică, noi știm că fiecare termen al secvenței Fibonacci este suma celor două numere precedente. Acest articol va prezenta câteva metode pentru a deduce o formulă închisă printr-o relație recursivă.

paşi

Metoda 1

2

Deoarece fiecare termen este dat de plusul precedent 3, acesta poate fi exprimat ca o recurență, așa cum se arată în figură.

3

Rețineți întotdeauna că orice reapariție a formulei a_n = a_n-1 + d este o secvență aritmetică.

4

Scrieți formula închisă ca o secvență aritmetică, eventual cu unele necunoscute așa cum se arată în figură.

5

Găsiți necunoscute pe baza modului în care începe formula. În acest caz, deoarece 5 este termenul 0, formula va fi a_n = 5 + 3n. Dacă, în schimb, doriți să luați în considerare 5 primul termen, va trebui_n = 2 + 3n.

Metoda 2

2

Deoarece fiecare termen este de două ori cel precedent, el poate fi exprimat ca o relație recursivă utilizând formula prezentată în figură.

3

Știm că fiecare reapariție a formulei a_n = r * a_(N-1) este o secvență geometrică.

4

Scrie formula închisă pentru o secvență geometrică, posibil cu unele necunoscute așa cum se arată.

5

Rezolvați necunoscute pe baza modului în care începe formula. În acest caz, 3 este termenul 0, astfel încât formula va deveni a_n = 3 * 2ⁿ. Având în vedere că 3 este primul termen, ar trebui să ajungeți în schimb_n = 3 * 2^(N-1).

Metoda 3

2

Fiecare apariție a formula arătată, și anume acelea în care p (n) este orice polinom în n, va avea o formulă polinom închisă a unui grad mai ridicat la gradul de p.

3

Scrieți formula generală a unui polinom de gradul necesar. În acest exemplu, p este un pătrat, deci veți avea nevoie de un exponent cubic pentru a reprezenta secvența a_n.

4

Deoarece un cub generic are patru coeficienți necunoscuți, sunt necesari patru termeni ai secvenței pentru a rezolva sistemul rezultat. Fiecare dintre cele patru poate face acest lucru, astfel încât să puteți utiliza termenii 0, 1, 2 și 3. Du-te înapoi cu recurența pentru a găsi termenul -1 ar putea da o soluție mai ușor de sistem, dar nu este necesar.

5

Rezolvați sistemul rezultat al ecuațiilor de grad "deg (p) +2" cu un număr de necunoscute egal cu "deg (p) = 2" așa cum este ilustrat în figură.

6

dacă "la" a fost unul dintre termenii pe care i-ați folosit pentru a rezolva coeficienții, veți obține termenul constant al polinomului și vă va permite să reduceți sistemul la o ecuație de grad "deg (p) +1" cu un număr de necunoscute egal cu "deg (p) +1" (vezi figura).

7

Rezolvați sistemul de ecuații liniare pentru a obține c₃ = 1/3, c₂ = -5 / 2, c₁ = -17 / 6 și c = 5. Reprezintă formula închisă pentru a_n ca polinom cu coeficienți cunoscuți.

Metoda 4

2

Scrieți polinomul caracteristic al recurenței. Se obține prin înlocuirea fiecărui a_n la aniversarea cu xⁿ și împărțirea cu x^(N-k) obținând un monomial de grad k și un termen constant diferit de zero.

3

Rezolvați polinomul caracteristic. În acest caz, caracteristica este de gradul doi, deci este posibil să se folosească formula lui ecuațiile etajate pentru a-și găsi rădăcinile.

4

Fiecare expresie a formulei indicate satisface recurența. C este o constantă și baza exponenților sunt rădăcinile caracteristicilor calculate în etapa anterioară. Se poate verifica prin inducție.

5

Calculați termenul c care îndeplinește condițiile inițiale specifice. Ca și în cazul polinomului, acest rezultat se obține prin crearea unui sistem liniar de ecuații din termenii inițiale. Deoarece exemplul are două necunoscute, vor fi necesari doi termeni. Nu contează care dintre ele, astfel încât să puteți lua termenii 0 și 1 pentru a evita să vă ridicați un număr irațional la o putere prea mare.

6

Rezolvați sistemul de ecuații rezultat.

7

Introduceți constantele obținute în formula generală ca soluție.

Metoda 5

2

Scrieți funcția de generare a secvenței. O funcție generatoare este pur și simplu o serie formată de puteri a căror coeficient de xⁿ acesta este ultimul termen al secvenței.

3

Modificați funcția de generare așa cum se arată în figură. Scopul în acest moment este de a găsi o ecuație care vă permite să rezolvați funcția de generare A (x). Extrageți termenul inițial. Aplicați formula de recurență termenilor care rămân. Împărțiți suma. Extrageți termenii constanți. Utilizați definiția lui A (x). Utilizați formula pentru suma unei serii geometrice.

4

Obțineți funcția de generare A (x).

5

Obțineți coeficientul de xⁿ în A (x). Metodele pentru obținerea schimba în funcție de ceea ce arata ca A (x), dar din fracțiile parțiale, combinate cu cunoașterea funcției de generare a unei secvențe geometrice, este prezentată în figură.

6

Scrieți formula pentru a_n identificarea coeficientului de xⁿ în A (x).