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).
Czytaj dalej
Powiązane artykuły
Logika i dyskretnaĆwiczenia z logicznych inwersji i negacji zdań
Logika i dyskretnaLogika predykatów: przykłady i zapisy formalne
Logika i dyskretnaPodstawy grafów: zadanie o ścieżkach i przykład rozwiązania
Logika i dyskretnaRelacje i funkcje w ujęciu dyskretnym — zadania z rozwiązaniem
Logika i dyskretnaKombinatoryka dla maturzysty: permutacje i kombinacje
Logika i dyskretnaDowody i kontrprzykłady — jak pisać poprawne argumenty


