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

Στα μαθηματικά, η γραμμική αναδρομική ακολουθία πρώτης τάξης είναι η ακολουθία $u_{1},u_{2},\ldots$ η οποία ικανοποιεί την αναδρομική σχέση

$u_{n+1}=\lambda \cdot u_{n}+\omega$, για κάθε $n\geq 1$,

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

Ειδικές περιπτώσεις αυτής της εξίσωσης είναι η αριθμητική πρόοδος για $\lambda =1$ και η γεωμετρική πρόοδος για $\omega =0$.

Ισοδύναμα, ο γενικός τύπος για τον $n$-οστό όρο δίνεται από

$u_{n}=\lambda ^{n-1}\cdot \left(u_{1}-{\frac {\omega }{1-\lambda }}\right)+{\frac {\omega }{1-\lambda }}$, αν $\lambda \neq 1$

και

$u_{n}=u_{1}+(n-1)\cdot \omega$, αν $\lambda =1$.

Ισοδυναμία ορισμών

Γενικός σε αναδρομικό τύπο

Απόδειξη  

(Περίπτωση $\lambda \neq 1$) Ξεκινώντας από τον γενικό τύπο έχουμε ότι

${\begin{aligned}u_{n+1}&=\lambda ^{n}\cdot \left(u_{1}-{\frac {\omega }{1-\lambda }}\right)+{\frac {\omega }{1-\lambda }}\\&=\lambda \cdot \left(\lambda ^{n-1}\cdot \left(u_{1}-{\frac {\omega }{1-\lambda }}\right)+{\frac {\omega }{1-\lambda }}\right)-{\frac {\omega \lambda }{1-\lambda }}+{\frac {\omega }{1-\lambda }}\\&=\lambda \cdot u_{n}+\omega \cdot {\frac {1-\lambda }{1-\lambda }}\\&=\lambda \cdot u_{n}+\omega .\end{aligned}}$

(Περίπτωση $\lambda =1$)

$u_{n+1}=u_{1}+(n-1)\cdot \omega =(u_{1}+(n-2)\cdot \omega )+\omega =u_{n-1}+\omega =\lambda \cdot u_{n-1}+\omega$.

Και στις δύο περιπτώσεις οδηγούμαστε στον αναδρομικό.

Αναδρομικός σε γενικό τύπο

Απόδειξη  

(Περίπτωση $\lambda \neq 1$) Για να αποδείξουμε τον γενικό τύπο από τον αναδρομικό, θα χρησιμοποιήσουμε την μέθοδο της μαθηματικής επαγωγής για όλους τους φυσικούς αριθμούς $\nu$.

Βασική Περίπτωση: Για $n=1$, έχουμε ότι

$u_{1}=\lambda ^{1-1}\cdot \left(u_{1}-{\frac {\omega }{1-\lambda }}\right)+{\frac {\omega }{1-\lambda }}=u_{1}$.

Επαγωγική Περίπτωση: Αν ισχύει για $\nu =\kappa$, δηλαδή $u_{\kappa }=\lambda ^{\kappa -1}\cdot \left(u_{1}-{\frac {\omega }{1-\lambda }}\right)+{\frac {\omega }{1-\lambda }}$, θα δείξουμε ότι ισχύει και για $\nu =\kappa +1$. Από τον αναδρομικό τύπο,

${\begin{aligned}u_{\kappa +1}&=\lambda \cdot u_{\kappa }+\omega \\&=\lambda \cdot \left(\lambda ^{\kappa -1}\cdot \left(u_{1}-{\frac {\omega }{1-\lambda }}\right)+{\frac {\omega }{1-\lambda }}\right)+\omega \\&=\lambda ^{\kappa }\cdot \left(u_{1}-{\frac {\omega }{1-\lambda }}\right)+{\frac {\omega \lambda }{1-\lambda }}+\omega \\&=\lambda ^{\kappa }\cdot \left(u_{1}-{\frac {\omega }{1-\lambda }}\right)+{\frac {\omega }{1-\lambda }}.\end{aligned}}$

Επομένως ισχύει και για $\nu =\kappa +1$ και έτσι για όλους τους φυσικούς αριθμούς $\nu$.

(Περίπτωση $\lambda =1$)

Βασική Περίπτωση: $u_{1}=u_{1}+(1-1)\cdot \omega$.

Επαγωγική Περίπτωση:

$u_{n+1}=u_{n}+\omega =u_{1}+(n-1)\cdot \omega +\omega =u_{1}+n\cdot \omega$.

Ιδιότητες

Για το άθροισμα $S_{n}=u_{1}+u_{2}+\ldots +u_{n}$, έχουμε ότι

$S_{n}={\frac {1-\lambda ^{n}}{1-\lambda }}\cdot \left(u_{1}-{\frac {\omega }{1-\lambda }}\right)+n\cdot {\frac {\omega }{1-\lambda }}$ αν $\lambda \neq 1$

και

$S_{n}=n\cdot u_{1}+{\frac {1}{2}}\omega \cdot (n-1)\cdot n$ αν $\lambda =1$.

Απόδειξη  

(Περίπτωση $\lambda \neq 1$)

${\begin{aligned}S_{n}&=\sum _{k=1}^{n}\left(\lambda ^{k-1}\cdot \left(u_{1}-{\frac {\omega }{1-\lambda }}\right)+{\frac {\omega }{1-\lambda }}\right)\\&=\left(u_{1}-{\frac {\omega }{1-\lambda }}\right)\cdot \sum _{k=1}^{n}\lambda ^{k-1}+n\cdot {\frac {\omega }{1-\lambda }}.\end{aligned}}$

Το άθροισμα στην τελευταία γραμμή είναι το άθροισμα των $n$ πρώτων όρων μίας γεωμετρικής προόδου με πρώτο όρο το $1$ και επομένως

$\left(u_{1}-{\frac {\omega }{1-\lambda }}\right)\cdot {\frac {1-\lambda ^{n}}{1-\lambda }}+n\cdot {\frac {\omega }{1-\lambda }}$.

(Περίπτωση $\lambda =1$)

${\begin{aligned}S_{n}&=\sum _{k=1}^{n}\left(u_{1}+(k-1)\cdot \omega \right)\\&=n\cdot u_{1}+\omega \cdot \sum _{k=1}^{n}(k-1)\end{aligned}}$

Το άθροισμα στην τελευταία γραμμή είναι το άθροισμα των $n$ πρώτων όρων μίας αριθμητικής προόδου με πρώτο όρο το $0$ και διαφορά $1$. Επομένως,

$S_{n}=n\cdot u_{1}+{\frac {1}{2}}\omega \cdot (n-1)\cdot n$.

Εφαρμογές

Πύργος του Ανόι

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

Παρακάτω δίνονται τα βέλτιστα βήματα για $n=3$:

← Προηγούμενο βήμα ← Προηγούμενο βήμα Επόμενο βήμα → Επόμενο βήμα → 1

Αν $x_{n}$ είναι το βέλτιστο πλήθος βημάτων για να μετακινηθούν $n$ δίσκοι από την πρώτη στήλη στην τελευταία, τότε

$x_{n}=$ (βήματα για τους $n-1$ δίσκους από την $1\to 2$)

+ (μετακίνηση του μεγάλου δίσκου στην $3$)

+ (βήματα για τους $n-1$ δίσκους από την $2\to 3$)

Δηλαδή,

$x_{n}=x_{n-1}+1+x_{n-1}=2x_{n-1}+1$,

καθώς και

$x_{1}=1$.

Επομένως το βέλτιστο πλήθος των κινήσεων είναι μία γραμμική αναδρομική ακολουθία με $\lambda =2$ και $\omega =1$. Άρα ο γενικός τύπος δίνει

${\begin{aligned}x_{n}&=2^{n-1}\cdot \left(1-{\frac {1}{1-2}}\right)+{\frac {1}{1-2}}\\&=2^{n}-1\end{aligned}}$.

Αλυσίδες Μάρκοφ

Αλυσίδα Μαρκόφ με δύο καταστάσεις

Έστω μία αλυσίδα Μάρκοφ με δύο καταστάσεις ${\rm {A}}$ και ${\rm {B}}$, και $p$ η πιθανότητα να μετακινηθούμε από το ${\rm {A\to B}}$ και $q$ η πιθανότητα να μετακινηθούμε από το ${\rm {B\to A}}$. Αν $p_{n}$ η πιθανότητα να είμαστε στο ${\rm {A}}$ μετά από $n$ βήματα (και $q_{n}$ να είμαστε στο ${\rm {B}}$), τότε έχουμε ότι

$p_{n}=$ (ήμασταν στο ${\rm {A}}$ και μείναμε στο ${\rm {A}}$) + (ήμασταν στο ${\rm {B}}$ και πήγαμε στο ${\rm {A}}$)

${\begin{aligned}{\phantom {p_{n}}}&=p_{n-1}\cdot (1-p)+q_{n}\cdot q\\&=p_{n-1}\cdot (1-p)+(1-p_{n})\cdot q\\&=p_{n-1}\cdot (1-p-q)+q,\end{aligned}}$

που ορίζει μία γραμμική αναδρομική ακολουθία πρώτης τάξης. Επομένως, αν $p+q\neq 0$, ο $n$-οστός όρος είναι

$p_{n}=(1-p-q)^{n-1}\cdot \left(p_{1}-{\frac {q}{p+q}}\right)+{\frac {q}{p+q}}$.

Από αυτόν τον τύπο, παίρνοντας το όριο καθώς $n\to \infty$ προκύπτει και η αναλοίωτη κατανομή της αλυσίδας

$\pi ={\begin{pmatrix}{\frac {q}{p+q}}\\{\frac {p}{p+q}}\end{pmatrix}}$.

Δείτε επίσης

• Αριθμητική πρόοδος
• Γεωμετρική πρόοδος
• Μικτή πρόοδος
• Γραμμική αναδρομική ακολουθία δεύτερης τάξης