Γραμμική αναδρομική ακολουθία δεύτερης τάξης

Στα μαθηματικά,  **γραμμική αναδρομική ακολουθία δεύτερης τάξης** είναι η ακολουθία u_0, u_1, u_2, \ldots η οποία ικανοποιεί την αναδρομική σχέση
:u_n = a \cdot u_{n-1} + b \cdot u_{n-2} + c,  για κάθε n \geq 2
για σταθερές a, b, c (με b \neq 0), δηλαδή που δεν εξαρτώνται από το n.

Το πιο γνωστό παράδειγμα είναι η ακολουθία Φιμπονάτσι f_0, f_1, f_2, \ldots, η οποία ικανοποιεί την αναδρομική σχέση για a = b = 1 και c = 0, δηλαδή 
:f_n = f_{n-1} + f_{n-2} για κάθε n \geq 2 
και επίσης f_0 = 0, f_1 = 1. 

Ακολουθίες αυτής της μορφής εμφανίζονται σε αρκετούς κλάδους των καθαρών και εφαρμοσμένων μαθηματικών, όπως στην συνδυαστική για την καταμέτρηση αντικειμένων, και στην θεωρία πιθανοτήτων (δείτε εφαρμογές).  

## Παραδείγματα

### Παράδειγμα 1ο: Ακολουθία Φιμπονάτσι
Όπως αναφέραμε παραπάνω, η ακολουθία Φιμπονάτσι είναι η ακολουθία που ικανοποιεί την σχέση 
:f_n = f_{n-1} + f_{n-2} για κάθε n \geq 2 
και επίσης f_0 = 0, f_1 = 1. Αυτά είναι αρκετά για να υπολογίσουμε όλους τους όρους της ακολουθίας ως εξής
:\begin{align}
f_0 &= 0 \\
f_1 &= 1 \\
f_2 &= f_1 + f_0 = 1 + 0 = 1 \\
f_3 &= f_2 + f_1 = 1 + 1 = 2 \\
f_4 &= f_3 + f_2 = 2 + 1 = 3 \\
f_5 &= f_4 + f_3 = 3 + 2 = 5 \\
f_6 &= f_5 + f_4 = 5 + 3 = 8 \\
f_7 &= f_6 + f_5 = 8 + 5 = 13\\
f_8 &= f_7 + f_6 = 13 + 8 = 21\\
& \vdots
\end{align}

### Παράδειγμα 2ο
Θεωρούμε την ακολουθία (u_n)_{n = 0}^{\infty} με αναδρομιή σχέση 
:u_n = 4u_{n-1} - 4u_{n-2} για κάθε n \geq 2 
και επίσης u_0 = 3, u_1 = 8. Ξανά μπορούμε να υπολογίσουμε τους όρους της ως εξής:
:\begin{align}
u_0 &= 3 \\
u_1 &= 8 \\
u_2 &= 4u_1 - 4u_0 = 4 \cdot 8 - 4 \cdot 3 = 20 \\
u_3 &= 4u_2 - 4u_1 = 4 \cdot 20 - 4 \cdot 8 = 48 \\
u_4 &= 4u_3 - 4u_2 = 4 \cdot 48 - 4 \cdot 20 = 112 \\
 &  \vdots
\end{align}

## Γενικός τύπος για ''c=0''

Η χαρακτηριστική της εξίσωση είναι το τριώνυμο 
:x^2 - ax + b = 0
Έστω \rho_1, \rho_2 οι ρίζες της χαρακτηριστικής εξίσωσης, τότε 
* Αν \rho_1 \neq \rho_2
::u_n = \frac{\rho_1^n - \rho_2^n}{\rho_1 - \rho_2} \dot u_1 + \frac{\rho_1^n \rho_2 - \rho_1 \rho_2^n}{\rho_1 - \rho_2} \cdot u_0.
* Αν \rho_1 = \rho_2 = \rho
::u_n = n \cdot \rho^{n-1} \cdot u_1  - (n-1) \cdot \rho^n \cdot u_0.

 \cdot u_0 - \rho_1^n \rho_2 \cdot u_0 +  \rho_1^n \cdot u_1 - \rho_2^n \cdot u_1 - \cancel{\rho_1^{n+1}} \cdot u_0 + \rho_1 \rho_2^n \cdot u_0}{\rho_1 - \rho_2} \\
 & = \frac{\rho_1^n - \rho_2^n}{\rho_1 - \rho_2} \cdot u_1 + \frac{\rho_1 \rho_2^n - \rho_1^n \rho_2}{\rho_1 - \rho_2} \cdot u_0.
\end{align}

**Περίπτωση 2η [<math>\rho_1 = \rho_2 = \rho</math>]:** Σε αυτή την περίπτωση όλοι οι όροι του δεύτερου όρου είναι ίσοι, άρα
:\begin{align}
u_n 
 & = \rho^n \cdot u_0 + n \cdot \rho^{n-1} \cdot v_1\\
 & =  n \cdot \rho^{n-1} \cdot u_1 - (n-1) \cdot \rho^n \cdot u_0.
\end{align}
}}
Πιο απλά, το παραπάνω θεώρημα λέει ότι αν \rho_1 \neq \rho_2
:u_n = A \rho_1^n + B \rho_2^n 
για κάποιες σταθερές A, B που προσδιορίζονται από τις τιμές των u_0, u_1,
και αν \rho_1 = \rho_2 = \rho, τότε
:u_n = A \rho^n \cdot n + B \rho^n.

## Παράδειγμα

### Διακριτές ρίζες (Ακολουθία Φιμπονάτσι)

Η χαρακτηριστική εξίσωση για την ακολουθία Φιμπονάτσι είναι
:x^2 -x -1=0, 
η οποία έχει ρίζες 
:\rho_1 = \frac{1 - \sqrt{5}}{2} και \rho_2 = \frac{1 + \sqrt{5}}{2}.
Χρησιμοποιώντας τον παραπάνω γενικό τύπο, έχουμε ότι 
:u_n = \frac{\rho_1^n - \rho_2^n}{\rho_1 - \rho_2} = \frac{1}{\sqrt{5}} \cdot \left( \left(\frac{1 + \sqrt{5}}{2} \right)^n - \left(\frac{1 - \sqrt{5}}{2} \right)^n \right)

### Διπλή ρίζα
Θεωρούμε την ακολουθία με αναδρομική σχέση 
:u_n = 4u_{n-1} - 4u_{n-2}
και u_0 = 3 και u_1 = 8. 

Η χαρακτηριστική της εξίσωση είναι 
:x^2 - 4x + 4 = (x-2)^2 = 0,  
η οποία έχει διπλή ρίζα το x = 2.

Χρησιμοποιώντας τον παράνω γενικό τύπο, έχουμε ότι 
:
\begin{align}
u_n 
 & = n \cdot 2^{n-1} \cdot 8 - (n-1) \cdot 2^n \cdot 3\\ 
 & =(n + 3) \cdot 2^n . 
\end{align}

## Ως σχέση διανυσμάτων

### Για ''c=0''

Η γραμμική αναδρομική ακολουθία δεύτερης τάξης με c = 0 μπορεί να γραφτεί ως η εξής αναδρομική σχέση μεταξύ διανυσμάτων 
:
 \begin{bmatrix}
u_{n+1} \\
u_n
 \end{bmatrix}
 = \begin{bmatrix}
 a & b \\
 1 & 0
 \end{bmatrix} \cdot
 \begin{bmatrix}
  u_n \\
  u_{n-1}
  \end{bmatrix}
 για κάθε n \geq 1.

Από αυτήν την σχέση έπεται ότι 
:
 \begin{bmatrix}
u_{n+1} \\
u_n
 \end{bmatrix}
 = \begin{bmatrix}
 a & b \\
 1 & 0
 \end{bmatrix} \cdot
 \left( \begin{bmatrix}
 a & b \\
 1 & 0
 \end{bmatrix} \cdot
 \begin{bmatrix}
  u_{n-1} \\
  u_{n-2}
  \end{bmatrix}
  \right) 
  = \ldots = \begin{bmatrix}
 a & b \\
 1 & 0
 \end{bmatrix}^{n-1}
 \cdot 
 \begin{bmatrix}
  u_1 \\
  u_0
  \end{bmatrix}

που όπως θα δούμε παρακάτω είναι χρήσιμη για τον αποδοτικό (και ακριβή) υπολογισμό των γενικών όρων. 

Διαγωνιοποιώντας τον πίνακα
:\begin{bmatrix}
 a & b \\
 1 & 0
 \end{bmatrix} = PDP^{-1},
όπου P, D \in \R^{2 \times 2} και D ένας διαγώνιος πίνακας, έχουμε ότι 
: \begin{bmatrix}
u_{n+1} \\
u_n
 \end{bmatrix}
 = \begin{bmatrix}
 a & b \\
 1 & 0
 \end{bmatrix}^{n-1}
 \cdot 
 \begin{bmatrix}
  u_1 \\
  u_0
  \end{bmatrix}
 = \underbrace{(PDP^{-1}) \cdot \ldots \cdot (PDP^{-1})}_{n \text{ φορές}} \cdot 
 \begin{bmatrix}
  u_1 \\
  u_0
  \end{bmatrix}
  = PD^nP^{-1} \cdot 
 \begin{bmatrix}
  u_1 \\
  u_0
  \end{bmatrix}
Καθώς η δύναμη ενός διαγώνιου πίνακα είναι εύκολο να υπολογιστεί, αυτή η σχέση μπορεί επίσης να μας δώσει τον γενικό τύπο για τον n-οστό όρο.

### Για ''c≠0''

Η γραμμική αναδρομική ακολουθία δεύτερης τάξης με c \neq 0 ικανοποιεί 
:
 \begin{bmatrix}
u_{n+1} \\
u_n \\
1
 \end{bmatrix}
 = \begin{bmatrix}
 a & b & c \\
 1 & 0 & 0 \\
 0 & 0 & 1
 \end{bmatrix} \cdot
 \begin{bmatrix}
  u_n \\
  u_{n-1} \\
  1
  \end{bmatrix}
 για κάθε n \geq 1.

## Εφαρμογές

Οι γραμμικές αναδρομικές σχέσεις έχουν εφαρμογές σε αρκετούς τομείς των μαθηματικών, όπως στην επίλυση προβλήματων στην θεωρία πιθανοτήτων και στην καταμέτρηση αντικειμένων στην συνδυαστική.

### Μαρκοβιανές αλυσίδες
Θεωρούμε μία Μαρκοβιανή αλυσίδα όπου ο γράφος της είναι ένα μονοπάτι με n καταστάσεις, και οι πιθανότητες να μεταβούμε προς τα δεξιά είναι p και προς τα αριστερά είναι q αντίστοιχα. Από την πρώτη και την τελευταία κατάσταση μπορούμε μόνο να μείνουμε στις αντίστοιχες καταστάσεις.

Αν θέλουμε να υπολογίσουμε την πιθανότητα p_k να καταλήξουμε στην κατάσταση 1 ξεκινώντας από την κατάσταση k, τότε για κάθε κατάσταση \ell \neq 1, n. Θεωρούμε \mathcal{E} το γεγονός να φτάσουμε κάποια στιγμή στην κατάσταση 1 (και να μείνουμε εκεί). Τότε, έχουμε ότι 
:
\begin{align}
p_{\ell} 
 & = \Pr\left( \mathcal{E} \mid X_t = \ell \right) \\
 & = \Pr\left( \mathcal{E} \mid X_{t+1} = \ell + 1 \right) \cdot \Pr\left( X_{t+1} = \ell + 1 \mid X_t = \ell \right) \\
  & \qquad   + \Pr\left( \mathcal{E} \mid X_{t+1} = \ell - 1 \right) \cdot \Pr\left( X_{t+1} = \ell - 1 \mid X_t = \ell \right) \\
 & = p_{\ell + 1} \cdot p + p_{\ell - 1} \cdot q,
\end{align}

και επιπλέον p_1 = 1 και p_n = 0. Επομένως, οι τιμές p_1, \ldots, p_n είναι μέρος μίας αναδρομικής ακολουθίας δεύτερης τάξης. 

Η ειδική περίπτωση με p = q = \frac{1}{2} είναι το πρόβλημα καταστροφής του τζογαδόρου.

### Συνδυαστική

Έστω ότι έχουμε την διάθεσή μας κόκκινα τετράγωνα διαστάσεων 1 \times 1, πράσινα ορθογώνια 1 \times 2 και μπλε 1 \times 2 και θέλουμε να μετρήσουμε με πόσους τρόπους μπορούμε να καλύψουμε ορθογώνιο 1 \times n. 

Έστω u_n το πλήθος των τρόπων να καλύψουμε ένα ορθογώνιο διαστάσεων 1 \times n. Τότε, u_1 = 1 και u_2 = 3.

Για την αναδρομική σχέση αρκεί να παρατηρήσουμε ότι για το τελευταίο ορθογώνιο που τοποθετήσαμε υπάρχουν τρεις επιλογές: τοποθετήσαμε (1) το κόκκινο, (2) το πράσινο ή (3) το μπλε ορθογώνιο. Στην πρώτη περίπτωση το υπόλοιπο ορθογώνιο είναι 1 \times (n-1), ενώ στην δεύτερη και στην τρίτη είναι 1 \times (n-2). Από την προσθετική αρχή απαρίθμησης καθώς οι τρεις περιπτώσεις είναι ανεξάρτητες, έχουμε ότι 
:u_n = {\color{red} u_{n-1}} + {\color{green} u_{n-2}} + {\color{blue} u_{n-2}} = u_{n-1} + 2u_{n-2},
που είναι μία γραμμική αναδρομική σχέση δεύτερης τάξης. 

Χρησιμοποιώντας τον παραπάνω γενικό τύπο έχουμε ότι 
:u_n = \frac{2}{3} \cdot 2^{n} + \frac{1}{3} \cdot (-1)^n.

## Υπολογισμός

### Αναδρομική υλοποίηση
Η παρακάτω υλοποίηση υπολογίζει τον n-οστό όρο με αναδρομή. Σε κάθε κλήση κάνει (περίπου) δύο καινούργιες κλήσεις και επομένως χρειάζεται εκθετικό πλήθος προσθέσεων και αφαιρέσεων, που συνήθως είναι αργό για μεγάλες τιμές του n.


```c++
// Αναδρομική εύρεση n-οστού όρου.
double get_term_recursive(double a, double b, double u0, double u1, int n) {
   if (n == 0) return u0;
   if (n == 1) return u1;
   return a * get_term_recursive(a, b, u0, u1, n-1) 
      + b * get_term_recursive(a, b, u0, u1, n-2);
}
```


### Γραμμική υλοποίηση
Η παρακάτω υλοποίηση βρίσκει τον n-οστό όρο, βρίσκοντας διαδοχικά τους όρους u_2, u_3, \ldots, u_n. Χρειάζεται \Theta(n) προσθέσεις και πολλαπλασιασμούς.


```c++
// Εύρεση n-οστού όρου με επανάληψη.
double get_term_iterative(double a, double b, double u0, double u1, int n) {
   if (n == 0) return u0;
   if (n == 1) return u1;
   double un = u1, u_prev = u0;
   for (int i = 2; i <= n; ++i) {
      double u_next = a * un + b * u_prev;
      u_prev = un;
      un = u_next;
   }
   return un;
}
```


### Με τον γενικό τύπο

Η παρακάτω υλοποίηση χρησιμοποιεί τον γενικό τύπο που βρήκαμε παραπάνω για τον υπολογισμό του n-οστού όρου. Χρησιμοποιεί ύψωση σε δύναμη που χρειάζεται O(\log n) προσθέσεις και πολλαπλασιασμούς.


```c++
// Λύση του τριωνύμου x^2 -ax + b = 0.
std::pair<double, double> get_roots(double a, double b) {
   double sqrt_D = sqrt(a*a + 4 * b);
   return { (a-sqrt_D)/2, (a + sqrt_D)/2 };
}

// Εύρεση n-οστού όρου με την 
double get_term_closed_form(double a, double b, double u0, double u1, int n) {
   auto [r1, r2] = get_roots(a, b);
   if (r1 != r2) { // Περίπτωση 1η: Δύο διακριτές ρίζες. 
      double r1_n = std::pow(r1, n);
      double r2_n = std::pow(r2, n);
      return (r1_n - r2_n) / (r1 - r2) * u1 + (r1_n * r2 - r1 * r2_n) / (r2 - r1) * u0; 
   }
   // Περίπτωση 2η: Διπλή ρίζα.   
   double r_n_minus_1 = std::pow(r1, n-1);
   double r_n = r_n_minus_1 * r1;
   return n * r_n_minus_1 * u1 + r_n * (1 - n) * u0;
}
```


### Με χρήση πινάκων
Η παρακάτω υλοποίηση χρησιμοποιεί την αναδρομική σχέση με τους πίνακες που διατυπώσαμε παραπάνω για τον υπολογισμό του n-οστού όρου. Χρειάζεται επίσης O(\log n) προσθέσεις και πολλαπλασιασμούς. Επιπλέον έχει το πλεονέκτημα ότι αν οι αρχικοί όροι u_0, u_1 και οι σταθερές a, b είναι ακέραιοι, τότε δεν χρειάζεται να χρησιμοποιήσει δεκαδικούς αριθμούς. Αυτό σημαίνει ότι είναι πιο αποδοτικός ο αλγόριθμος και το αποτέλεσμα πιο ακριβές. 

```c++
// Πολλαπλασιασμός πινάκων.
Matrix2D multiply(Matrix2D x, Matrix2D y) {
   return { x.a11 * y.a11 + x.a12 * y.a21, x.a11 * y.a12 + x.a12 * y.a22, 
            x.a21 * y.a11 + x.a22 * y.a21, x.a21 * y.a12 + x.a22 * y.a22 };
}

// Εύρεση n-οστού όρου με την χρήση πινάκων.
double get_term_matrix(double a, double b, double u0, double u1, int n) {
   if (n == 0) return u0;
   // Δυαδική εκθετοποίηση πίνακα.
   Matrix2D A = { a, b, 1, 0 }, ans = {1, 0, 0, 1};
   --n;
   while (n > 0) {
      if (n % 2 == 1) ans = multiply(ans, A);
      n /= 2;
      A = multiply(A, A);
   }
   // Πολλαπλασιασμός με αρχικό διάνυσμα.
   return ans.a11 * u1 + ans.a12 * u0;
}
```


## Δείτε επίσης
* Γραμμική αναδρομική ακολουθία πρώτης τάξης
* Ακολουθία Φιμπονάτσι

## Σημειώσεις


## Παραπομπές


Κατηγορία:Ακολουθίες