.
Η μαθηματική επαγωγή, ή διαφορετικά τέλεια επαγωγή, είναι μια μέθοδος μαθηματικής απόδειξης που συνήθως χρησιμοποιείται για να αποδειχτεί ότι μια πρόταση ισχύει για όλους τους φυσικούς αριθμούς. Η μαθηματική επαγωγή είναι λογικά ισοδύναμη με την αρχή της καλής διάταξης.
Η μέθοδος της μαθηματικής επαγωγής δεν πρέπει να αντιμετωπίζεται σαν κάποιο είδος επαγωγικού λογισμού ο οποίος δεν οδηγεί πάντα σε έγκυρα αποτελέσματα, όπως για παράδειγμα στη φυσική όπου χρησιμοποιείται επαγωγικός λογισμός για να εξαχθεί ένας γενικός κανόνας από μερικές περιπτώσεις. Για την ακρίβεια η μέθοδος της μαθηματικής επαγωγής είναι μια μορφή παραγωγικού λογισμού και οδηγεί σε πλήρως κατοχυρωμένα αποτελέσματα.
Ολες οι προτάσεις που αποδεικνύονται με μαθηματική επαγωγή εξαρτώνται από ένα φυσικό αριθμό, ας πούμε τον αριθμό ν. Για παράδειγμα η πρόταση:
\( 1 + 2 + 3 + \cdots + \nu = \frac{\nu(\nu + 1)}{2} \)
Η πρώτη γνωστή απόδειξη με τη μέθοδο της μαθηματικής επαγωγής εμφανίζεται στο έργο Arithmeticorum libri duo του Ιταλού μαθηματικού και αστρονόμου Franciscus Maurolycus του 16ου αιώνα. Συγκεκριμένα χρησιμοποίησε τη μέθοδο για να αποδείξει ότι το άθροισμα των ν πρώτων περιττών αριθμών είναι ν2.
Περιγραφή της μεθόδου
Είναι βολικό να μιλούμε για την πρόταση προς απόδειξη συμβολίζοντας την με P(ν) και αντικαθιστώντας όπου ν τον αριθμό που θέλουμε.
Η πιο απλή και πιο συνήθης μορφή της μεθόδου είναι αυτή που αποδεικνύει ότι μια πρόταση P(ν) είναι αληθής για όλους τους φυσικούς αριθμούς ν και αποτελείται από τα παρακάτω τρία βήματα:
1. Βασικό βήμα: δείχνουμε ότι η πρόταση P(ν) ισχύει για ν = 1,
2. Επαγωγική υπόθεση: υποθέτουμε ότι η πρόταση P(ν) είναι αληθής για κάποιο ν = κ, δηλαδή ότι ισχύει P(κ).
3. Επαγωγικό βήμα: χρησιμοποιώντας την επαγωγική υπόθεση προσπαθούμε να αποδείξουμε ότι αν η πρόταση ισχύει για ν = κ τότε ισχύει και για ν = κ + 1 δηλαδή ότι: ξεκινώντας από την υπόθεση ότι ισχύει P(κ) καταλήγουμε ότι ισχύει P(κ + 1).
Με το επαγωγικό βήμα έχουμε καταφέρει να αποδείξουμε ότι, αν η πρόταση είναι αληθής για κάποιο φυσικό αριθμό ν = κ, τότε είναι αληθής και για κάθε επόμενο φυσικό αριθμό. Από το βασικό βήμα όμως έχουμε ήδη αποδείξει ότι ένας τέτοιος αριθμός (για τον οποίο η πρόταση είναι αληθής) υπάρχει και είναι ο ν = 1. Επομένως η πρόταση ισχύει για όλους τους φυσικούς αριθμούς καθώς όλοι τους είναι ίσοι με τον προηγούμενο αυξημένο κατά ένα.
Είναι βοηθητικό να σκέφτεται κανείς την μαθηματική μέθοδο σε αναλογία με μια σειρά από ντόμινο τοποθετημένα όρθια το ένα πολύ κοντά στο άλλο και θεωρήσουμε πως ισχύουν οι παρακάτω προϋποθέσεις :
Αν σπρώξουμε το πρώτο ντόμινο στη σειρά, αυτό θα πέσει.
Όταν ένα οποιοδήποτε από τα ντόμινο πέσει τότε πέφτει και το επόμενο.
Έτσι μπορούμε να είμαστε απόλυτα βέβαιοι ότι αν σπρώξουμε το πρώτο ντόμινο για να πέσει τότε όλα τα ντόμινο θα πέσουν. Από το βιβλίο Μαθηματικά Θετικής-Τεχνολογικής κατεύθυνσης Β' Λυκείου διαβάζουμε:
Παράδειγμα
Ας υποθέσουμε ότι θέλουμε να αποδείξουμε την πιο κάτω μαθηματική πρόταση (την οποία θα συμβολίσουμε με P(ν)) :
\( 1 + 2 + 3 + \cdots + \nu = \frac{\nu(\nu + 1)}{2} \)
για κάθε \( \nu \in \mathbb{N} \)
Η πιο πάνω πρόταση είναι ένας τύπος που χρησιμοποιείται για την πρόσθεση όλων των φυσικών αριθμών από 1 μέχρι ν. Η απόδειξη της πρότασης γίνεται με τη μέθοδο της μαθηματικής επαγωγής ως ακολούθως:
Ελέγχουμε ότι η πρόταση ισχύει για ν = 1, [επαληθεύουμε δηλαδή ότι ισχύει η P(1)]. Είναι προφανές ότι το άθροισμα των πρώτων 1 φυσικών αριθμών είναι 1.
\( 1 = \frac{1(1+ 1)}{2} = 1 \)
Στη συνέχεια υποθέτουμε ότι η πρόταση είναι αληθής για κάποιο φυσικό αριθμό ν = κ [δηλαδή ότι η P(κ) είναι αληθής].
\( 1 + 2 + 3 + \cdots + \kappa = \frac{\kappa(\kappa + 1)}{2} \), (επαγωγική υπόθεση)
Τέλος προσπαθούμε να αποδείξουμε ότι, αν η πρόταση ισχύει για ν = κ, τότε ισχύει και για ν = κ + 1, [αν ισχύει η P(κ), τότε ισχύει και η P(κ + 1)] δηλαδή ότι:
\( 1 + 2 + 3 + \cdots + \kappa + 1 = \frac{(\kappa + 1)(\kappa + 2)}{2} \)
Το κάνουμε αυτό χρησιμοποιώντας την επαγωγική υπόθεση. Έχουμε δεχτεί ότι ισχύει:
\( 1 + 2 + 3 + \cdots + \kappa = \frac{\kappa(\kappa + 1)}{2} \)
Προσθέτουμε και στα δύο μέλη της εξίσωσης τον όρο κ + 1, που είναι ο επόμενος του κ φυσικός αριθμός, και έχουμε διαδοχικά:
\( 1 + 2 + 3 + \cdots + \kappa + (\kappa + 1)= \frac{\kappa(\kappa + 1)}{2} + (\kappa + 1)
= \frac{\kappa(\kappa + 1)}{2} + \frac{2(\kappa + 1)}{2}
= \frac{(\kappa^2 + 3\kappa + 2)}{2}
= \frac{(\kappa + 1)(\kappa + 2)}{2} \)
Έτσι έχουμε:
\( 1 + 2 + 3 + \cdots + \kappa + (\kappa + 1) = \frac{(\kappa + 1)(\kappa + 2)}{2} \)
Αυτό που έχουμε καταφέρει είναι να δείξουμε ότι, αν η P(κ) είναι αληθής, τότε είναι αληθής και η P(κ + 1). Συμβολικά:
\( P(\kappa)\Rightarrow P(\kappa + 1) \)
Έτσι το μόνο που απομένει για να ολοκληρωθεί η απόδειξη είναι να βρούμε ένα φυσικό αριθμό κ για τον οποίο η P(κ) είναι αληθής. Τον αριθμό αυτό όμως τον έχουμε ήδη βρει και είναι ο αριθμός ν = κ = 1 για τον οποίο αποδείξαμε από την αρχή ότι ισχύει η P(1). Έτσι:
Ισχύει η P(1), δηλαδή η πρόταση είναι αληθής αν το ν έχει την τιμή 1.
Η P(ν) είναι αληθής αν ν = 1, επομένως η P(κ) είναι αληθής για κ = 1. Έχουμε όμως αποδείξει ότι, αν για κάποιο κ η P(κ) είναι αληθής, τότε είναι αληθής και η P(κ +1). Επομένως και η P(2) είναι αληθής.
Αν είναι αληθής η P(2) τότε είναι αληθής και η P(3), άρα και η P(4) και ούτω καθεξής.
4. Η πρόταση P(ν) είναι αληθής για όλους τους φυσικούς αριθμούς ν.
Άλλες μορφές επαγωγής
Η μαθηματική επαγωγή μπορεί να παρουσιάσει διαφορετικές μορφές ανάλογα με την περίπτωση. Αν θέλουμε να αποδείξουμε ότι μία πρόταση για όλους τους φυσικούς αριθμούς με μαθηματική επαγωγή μπορούμε να την αποδείξουμε εξειδικευμένα για κάποιους αριθμούς α,β,γ ή περισσότερους και έπειτα να αποδείξουμε τη συνεπαγωγή ή τις συνεπαγωγές. Η συνεπαγωγή δεν είναι ανάγκη να είναι της μορφής Π(ν)=>Π(ν+1), αλλά μπορεί να είναι και της μορφής Π(ν)=>Π(ν-1) ή ακόμα και της μορφής Π(ν)=>Π(ν+2), αν είναι απαραίτητο. Σημαντικό όμως είναι σε κάθε περίπτωση να εξασφαλιστεί ότι η επαγωγή διατρέχει το σύνολο που θέλουμε είτε είναι το σύνολο των φυσικών αριθμών ή κάποιο υποσύνολό του ή ακόμα και αν αναφέρεται στο σύνολο των ακεραίων.
Για παράδειγμα, αν θέλουμε να αποδείξουμε μια πρόταση όχι για όλους τους φυσικούς αριθμούς αλλά μόνο για αυτούς που είναι μεγαλύτεροι ή ίσοι με ένα συγκεκριμένο φυσικό αριθμό ν0, τότε είναι αρκετό να δείξουμε ότι:
Η πρόταση ισχύει για κάποιο φυσικό αριθμό ν0,
Αν η πρόταση ισχύει για κάποιο κ ≥ ν0 ισχύει και για το κ + 1,
για να έχουμε την πλήρη απόδειξη της πρότασης.
Για παράδειγμα, αυτή την μέθοδο χρησιμοποιούμε όταν θέλουμε να αποδείξουμε ότι: ν2 > 2ν για ν ≥ 3.
Πλήρης ή Ισχυρή Επαγωγή
Μια άλλη, ισχυρότερη αλλά ισοδύναμη, μορφή της επαγωγής είναι η εξής:
Αν η πρόταση ισχύει για κάθε k \le m, για κάποιο m ισχύει και για το m + 1.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
