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

Όπως αναφέραμε παραπάνω, η ακολουθία Φιμπονάτσι είναι η ακολουθία που ικανοποιεί την σχέση

${\displaystyle f_{n}=f_{n-1}+f_{n-2}}$ για κάθε ${\displaystyle n\geq 2}$

και επίσης ${\displaystyle f_{0}=0,f_{1}=1}$. Αυτά είναι αρκετά για να υπολογίσουμε όλους τους όρους της ακολουθίας ως εξής

${\displaystyle {\begin{aligned}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{aligned}}}$

Θεωρούμε την ακολουθία ${\displaystyle (u_{n})_{n=0}^{\infty }}$ με αναδρομιή σχέση

${\displaystyle u_{n}=4u_{n-1}-4u_{n-2}}$ για κάθε ${\displaystyle n\geq 2}$

και επίσης ${\displaystyle u_{0}=3,u_{1}=8}$. Ξανά μπορούμε να υπολογίσουμε τους όρους της ως εξής:

${\displaystyle {\begin{aligned}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{aligned}}}$

Η χαρακτηριστική εξίσωση για την ακολουθία Φιμπονάτσι είναι

${\displaystyle x^{2}-x-1=0}$,

η οποία έχει ρίζες

${\displaystyle \rho _{1}={\frac {1-{\sqrt {5}}}{2}}}$ και ${\displaystyle \rho _{2}={\frac {1+{\sqrt {5}}}{2}}}$.

Χρησιμοποιώντας τον παραπάνω γενικό τύπο, έχουμε ότι

${\displaystyle 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)}$

Θεωρούμε την ακολουθία με αναδρομική σχέση

${\displaystyle u_{n}=4u_{n-1}-4u_{n-2}}$

και ${\displaystyle u_{0}=3}$ και ${\displaystyle u_{1}=8}$.

Η χαρακτηριστική της εξίσωση είναι

${\displaystyle x^{2}-4x+4=(x-2)^{2}=0}$,

η οποία έχει διπλή ρίζα το ${\displaystyle x=2}$.

Χρησιμοποιώντας τον παράνω γενικό τύπο, έχουμε ότι

${\displaystyle {\begin{aligned}u_{n}&=n\cdot 2^{n-1}\cdot 8-(n-1)\cdot 2^{n}\cdot 3\\&=(n+3)\cdot 2^{n}.\end{aligned}}}$

Η γραμμική αναδρομική ακολουθία δεύτερης τάξης με ${\displaystyle c=0}$ μπορεί να γραφτεί ως η εξής αναδρομική σχέση μεταξύ διανυσμάτων

${\displaystyle {\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}}}$ για κάθε ${\displaystyle n\geq 1}$.

Από αυτήν την σχέση έπεται ότι

${\displaystyle {\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}}}$

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

Διαγωνιοποιώντας τον πίνακα

${\displaystyle {\begin{bmatrix}a&b\\1&0\end{bmatrix}}=PDP^{-1}}$,

όπου ${\displaystyle P,D\in \mathbb {R} ^{2\times 2}}$ και ${\displaystyle D}$ ένας διαγώνιος πίνακας, έχουμε ότι

${\displaystyle {\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^{n}P^{-1}\cdot {\begin{bmatrix}u_{1}\\u_{0}\end{bmatrix}}}$

Καθώς η δύναμη ενός διαγώνιου πίνακα είναι εύκολο να υπολογιστεί, αυτή η σχέση μπορεί επίσης να μας δώσει τον γενικό τύπο για τον ${\displaystyle n}$-οστό όρο.

Η γραμμική αναδρομική ακολουθία δεύτερης τάξης με ${\displaystyle c\neq 0}$ ικανοποιεί

${\displaystyle {\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}}}$ για κάθε ${\displaystyle n\geq 1}$.

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

Αν θέλουμε να υπολογίσουμε την πιθανότητα ${\displaystyle p_{k}}$ να καταλήξουμε στην κατάσταση ${\displaystyle 1}$ ξεκινώντας από την κατάσταση ${\displaystyle k}$, τότε για κάθε κατάσταση ${\displaystyle \ell \neq 1,n}$. Θεωρούμε ${\displaystyle {\mathcal {E}}}$ το γεγονός να φτάσουμε κάποια στιγμή στην κατάσταση ${\displaystyle 1}$ (και να μείνουμε εκεί). Τότε, έχουμε ότι

${\displaystyle {\begin{aligned}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{aligned}}}$

και επιπλέον ${\displaystyle p_{1}=1}$ και ${\displaystyle p_{n}=0}$. Επομένως, οι τιμές ${\displaystyle p_{1},\ldots ,p_{n}}$ είναι μέρος μίας αναδρομικής ακολουθίας δεύτερης τάξης.

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

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

Έστω ${\displaystyle u_{n}}$ το πλήθος των τρόπων να καλύψουμε ένα ορθογώνιο διαστάσεων ${\displaystyle 1\times n}$. Τότε, ${\displaystyle u_{1}=1}$ και ${\displaystyle u_{2}=3}$.^{[Σημείωση 2]}

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

${\displaystyle u_{n}={\color {red}u_{n-1}}+{\color {green}u_{n-2}}+{\color {blue}u_{n-2}}=u_{n-1}+2u_{n-2}}$,

που είναι μία γραμμική αναδρομική σχέση δεύτερης τάξης.

Χρησιμοποιώντας τον παραπάνω γενικό τύπο έχουμε ότι^{[Σημείωση 3]}

${\displaystyle u_{n}={\frac {2}{3}}\cdot 2^{n}+{\frac {1}{3}}\cdot (-1)^{n}}$.

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

// Αναδρομική εύρεση 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);
}

Η παρακάτω υλοποίηση βρίσκει τον ${\displaystyle n}$-οστό όρο, βρίσκοντας διαδοχικά τους όρους ${\displaystyle u_{2},u_{3},\ldots ,u_{n}}$. Χρειάζεται ${\displaystyle \Theta (n)}$ προσθέσεις και πολλαπλασιασμούς.

// Εύρεση 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;
}

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

// Λύση του τριωνύμου 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;
}

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

// Πολλαπλασιασμός πινάκων.
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;
}