Διατύπωση τού προβλήματος
Υποθέτουμε ότι θέλουμε να ανέβουμε μια σκάλα η οποία αποτελείται από σκαλοπάτια. Σε κάθε βήμα, ανεβαίνουμε είτε ακριβώς ένα σκαλί, είτε ακριβώς δύο σκαλιά. Με πόσους τρόπους μπορούμε να ανέβουμε τη σκάλα;
Για μικρά
- Για έχουμε τρόπο: –κάνουμε ένα βήμα μήκους .
- Για έχουμε τρόπους: –είτε κάνουμε δύο βήματα μήκους , είτε ένα βήμα μήκους .
- Για έχουμε τρόπους: .
- Για έχουμε τρόπους: .
Τι γίνεται όμως για μεγάλα
; Για
ας πούμε;
Φυσικά είναι σχεδόν αδύνατο να κάνει κανείς τον υπολογισμό όπως πριν. Θα
πρέπει να σκεφτούμε κάτι πιο έξυπνο, το οποίο μας δίνει απάντηση για
οποιοδήποτε
.
Αναδρομική σχέση
Συμβολίζουμε με το πλήθος των τρόπων να ανέβουμε μια σκάλα με σκαλοπάτια. Από τους προηγούμενους υπολογισμούς έχουμε
Το συνδυαστικό επιχείρημα: Όταν θέλουμε να ανεβούμε μια σκάλα με σκαλοπάτια, στο πρώτο βήμα είτε θα ανέβουμε ακριβώς σκαλί και μένουν άλλα τα οποία μπορούμε να ανέβουμε με τρόπους, είτε θα ανέβουμε ακριβώς σκαλιά και μένουν άλλα τα οποία μπορούμε να ανέβουμε με τρόπους. Συνεπώς, για έχουμε
Μια ακολουθία η οποία ικανοποιεί τις συνθήκες
λέγεται ακολουθία Fibonacci. Παρατηρούμε ότι για κάθε .
Ο τύπος της
Είτε με χρήση χαρακτηριστικού πολυωνύμου, είτε με επαγωγή, μπορούμε εύκολα να αποδείξουμε ότι για κάθε .
(Για διάφορες αποδείξης τού τύπου δες τους συνδέσμους στο τέλος)