Równanie rekurencyjne to takie równanie, które definiuje ciąg w sposób rekurencyjny. Zazwyczaj określona ona zależność pomiędzy dwoma kolejnymi wyrazami np. an + 1 = 2an, gdzie a1 = 2. W tym przypadku można łatwo wyprowadzić, że an = 2n. Czasem zdarzają się jednak bardziej skomplikowane przypadki takie jak np. ciąg Fibonacciego. Tym razem znalezienie wzoru ogólnego nie jest oczywiste.
Do rozwiązywania równań rekurencyjnych potrzebna jest funkcja solve_rec(), która jest dostępna w bibliotece o tej samej nazwie solve_rec. Bibliotekę należy dołączyć przed dalszymi obliczeniami:
| (%i1) | load(solve_rec); | |
| (%o1) | C:\maxima-5.37.3\share\maxima\solve_rec\solve_rec.mac |
Na początek rozpatrzmy przypadek podany we wstępie: an + 1 = 2an. Dodatkowo został podany warunek a1 = 2. Jednak tego typu równanie można rozwiązać bez warunku początkowego tj.:
| (%i3) | r1: a[n + 1] = 2*a[n]; roz: solve_rec(r1, a[n]); | |
| (roz) | an = %k12n |
W odpowiedzi otrzymaliśmy, że an = %k12n, gdzie %k1 jest to pewna wartość początkowa. Dla dowolnej wartości otrzymamy ciąg spełniający ustaloną na początku zależność.
Jednak jeśli pierwszy wyraz szukanego ciągu jest znany to wystarczy dopisać go do rozwiązywanego układu w następujący sposób:
| (%i3) | r1: a[n + 1] = 2*a[n]; roz: solve_rec(r1, a[n], a[1] = 2); | |
| (roz) | an = 2n |
W przypadku gdyby warunków początkowych byłoby więcej należałoby je dopisywać jako kolejne argumenty. Zostało to przedstawione w następnym przykładzie.
Analogicznie do poprzednich przykładów można rozwiązać równanie rekurencyjne ciągu Fibonacciego. Jest on określany równaniem an + 2 = an + 1 + an dla każdego n > 2 z dwoma warunkami początkowymi a1 = 1 i a2 = 1.
W celu rozwiązania tego układu należy wpisać:
| (%i7) | r1: a[n + 2] = a[n + 1] + a[n]; roz: solve_rec(r1, a[n], a[2] = 1, a[1] = 1); | |
| (roz) | an = |
W celu wyliczenia n-tego wyrazu ciągu na podstawie obliczonego rozwiązania roz można skorzystać z funkcji ev, która przyjmuje dwa argumenty. Jako pierwsze należy podać rozwiązanie zwrócone przez funkcję solve_rec(). Drugim arguementem musi być zmienna oraz jaka wartość ma zostać jej przypisana.
| (%i10) | r1: a[n + 1] = 2*a[n]; roz: solve_rec(r1, a[n], a[1] = 2); a10: ev(roz, n = 10); | |
| (a10) | a10 = 1024 |
Rozwiąż przy pomocy funkcji solve_rec() poniższy układ:
an + 2 = 2an + 1 + 3an
a1 = 3
a2 = 2
Następnie oblicz 10 wyraz podanego układu.