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

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

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

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

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

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

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

 Ιδιότητες 
Για το άθροισμα , έχουμε ότι 
 αν  
και
 αν .

 Εφαρμογές 

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

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

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

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

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

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

 Σημειώσεις 

 Παραπομπές 

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