Rekurencje proste i ich rozwiązania krok po kroku

3 min czytania
Rekurencje proste i ich rozwiązania krok po kroku

Wprowadzenie

Rekurencje to podstawa wielu zadań w matematyce dyskretnej i algorytmice. W najprostszym wydaniu mamy do czynienia z rekurencjami liniowymi rzędu pierwszego, które pojawiają się na zajęciach z logika-i-dyskretna oraz przy analizie złożoności algorytmów. Jeśli chcesz poćwiczyć podobne zagadnienia praktycznie, sprawdź także logika matematyczna zadania.

Co to są proste rekurencje liniowe

Prosta rekurencja liniowa rzędu pierwszego ma postać a_n = p * a_{n-1} + q, gdzie p i q są stałymi, a a_0 jest wartością początkową. Rozwiązanie polega zwykle na rozdzieleniu części jednorodnej i szczególnej.

W kontekście kursu warto także odwołać się do materiałów z zakresu matematyka dyskretna, które pokazują warianty i zastosowania takich rekurencji.

Rozwiązanie krok po kroku

Rozwiążmy konkretny przykład: a_n = 3 a_{n-1} + 2, z warunkiem początkowym a_0 = 1.

Krok 1 — część jednorodna: pomijamy stałą 2 i mamy a_n^(h) = 3 a_{n-1}^(h). Rozwiązanie jednorodne to a_n^(h) = C * 3^n.

Krok 2 — część szczególna: szukamy stałego rozwiązania a_n^(p) = A. Podstawiając: A = 3A + 2, stąd -2A = 2, więc A = -1.

Krok 3 — ogólne rozwiązanie: składamy obie części: a_n = C * 3^n – 1. Krok 4 — wykorzystujemy warunek początkowy: a_0 = C * 3^0 – 1 = C – 1 = 1, zatem C = 2. Ostatecznie:

a_n = 2 * 3^n – 1.

n a_n
0 1
1 5
2 14
3 41
4 122

Typowe uproszczenia i błędy

Przy rozwiązywaniu prostych rekurencji uczniowie często stosują krótsze ścieżki obliczeń, co jest dopuszczalne, ale warto być świadomym uproszczeń. Do najczęstszych należy:

  • pomijanie sprawdzenia warunku początkowego (prowadzi do błędnych stałych),
  • niepoprawne zgadywanie postaci rozwiązania szczególnego (np. gdy q ma postać wielomianu, należy przyjąć postać wielomianu tej samej klasy),
  • mylenie rzędu rekurencji — prosty wzór a_n = p a_{n-1} + q różni się od wzorów z opóźnieniami czy złożonymi współczynnikami.

W praktyce dobre nawyki z kursów z logika-i-dyskretna pomagają uniknąć tych pułapek — zapisuj po kolei część jednorodną, część szczególną, potem uwzględnij warunki początkowe.

Jak zapisywać rozwiązanie w czytelnej formie

Przejrzyste przedstawienie rozwiązania ułatwia ocenę i późniejsze wykorzystanie wyniku. Kilka wskazówek:

1) Na początku jasno podaj rekurencję i warunki początkowe. 2) Wypisz oddzielnie część jednorodną i szczególną. 3) Zapisz ogólne rozwiązanie, a następnie oblicz stałe z warunków początkowych. 4) Opcjonalnie przedstaw kilka pierwszych wartości (jak w tabeli powyżej) by zweryfikować wynik.

Taki sposób zapisu jest przydatny zarówno w zadaniach egzaminacyjnych, jak i w notatkach do dalszych analiz.

Czy rekurencje zawsze mają rozwiązanie?

Proste rekurencje liniowe rzędu pierwszego zawsze mają rozwiązanie postaci sumy części jednorodnej i szczególnej. Problemy pojawiają się przy rekurencjach nieliniowych lub z zależnymi warunkami początkowymi.

Jak sprawdzić poprawność wyniku?

Podstaw do równania kilka pierwszych wartości i sprawdź, czy zgadzają się z wyliczonym wzorem. Można też zastosować indukcję matematyczną jako dowód formalny.

Czy metoda działa dla p=1?

Tak, ale gdy p=1, część jednorodna ma postać C*1^n = C, więc trzeba znaleźć szczególne rozwiązanie odpowiednio, często prowadzi to do wzorów liniowych w n.

Tekst został utworzony przy pomocy sztucznej inteligencji (modeli językowych).

Redakcja Szkolnej Ściągi
Redakcja Szkolnej Ściągi

Redakcja przygotowuje treści, które ułatwiają zrozumienie matematyki na różnych poziomach nauki. Skupiamy się na jasnych wyjaśnieniach, praktycznych przykładach i materiałach pomocnych w powtórkach do egzaminów.